登录以参加训练计划

labuladong的算法网站 https://labuladong.online/algo/home/

labuladong的算法可视化 https://labuladong.online/zh/visualization/

labuladong学习路线（速成目录和题单） https://labuladong.online/algo/intro/quick-learning-plan/

labuladong速成学习规划路线讲解视频

https://labuladong.online/algo/intro/quick-learning-plan/

（注意labuladong这个网站的学习路线偏工作面试用的数据结构底层原理，优点是把数据结构的底层原理讲的比较举一反三，缺点是原网页用的是java语言代码较为繁琐 因为OI比赛更侧重理解题意和DP等算法思维的深度灵活运用，不单独考察基础数据结构等纯知识点理解，数据结构主要是结合在算法中用于把时间复杂度优化到极致）

总结一切数据结构和算法的顶层框架思维：

种种数据结构，皆为数组（顺序存储）和链表（链式存储）的变换。

• 数据结构的关键点在于遍历和访问，即增、删、查、改等基本操作。

• 种种算法，皆为穷举。

穷举的关键点在于无遗漏和无冗余。熟练掌握算法框架，可以做到无遗漏；充分利用信息，可以做到无冗余。

真正理解上面几句话，不仅本文 7000 字都不用看了，乃至本站的几十篇算法教程和习题都不用做了。

如果不理解，那么我就用下面的几千字，以及后面的几十篇文章和习题，来阐明上述的两句总结。大家在学习的时候，时刻品味这两句话，会大幅提高学习效率。

---

基于 Labuladong 的算法教程中关于前缀和 (Prefix Sum) 和差分数组 (Difference Array) 的内容，我为你总结了一份循序渐进的训练计划。 https://labuladong.online/algo/data-structure/prefix-sum/

这份计划从最基础的一维数组开始，过渡到二维矩阵，再延伸到差分数组（前缀和的逆运算），最后进阶到“前缀和+哈希表”的优化技巧。

---

第一阶段：基础概念与一维前缀和

核心知识点：

• 定义：preSum[i] 记录 nums[0...i-1] 的累加和。
• 公式：preSum[i] = preSum[i-1] + nums[i-1]。
• 作用：将“区间求和”的时间复杂度从 $O(N)$ 降低到 $O(1)$。主要用于处理数组元素不会改变的情况下的频繁查询。

必做题目：

1. LeetCode 303. 区域和检索 - 数组不可变 (Easy)

   • 训练目标：手写标准的前缀和构造，理解为什么 preSum 数组长度通常设为 n+1（为了处理索引 0 的边界情况）。
   • 关键公式：sumRange(i, j) = preSum[j+1] - preSum[i]。

2. LeetCode 724. 寻找数组的中心下标 (Easy)

   • 训练目标：灵活运用。中心索引左边的和等于右边的和。
   • 思路：左侧和 = totalSum - 左侧和 - 当前元素。

---

第二阶段：二维前缀和

核心知识点：

• 定义：preSum[i][j] 记录矩阵 (0,0) 到 (i-1, j-1) 构成的矩形区域元素之和。
• 容斥原理：计算任意子矩阵的和需要用到“加减法”来拼凑。

必做题目：

1. LeetCode 304. 二维区域和检索 - 矩阵不可变 (Medium)

   • 训练目标：掌握二维矩阵的构造与查询公式。
   • 关键公式：
     • 构造：pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i][j]
     • 查询：Sum(x1, y1, x2, y2) = pre[x2+1][y2+1] - pre[x1][y2+1] - pre[x2+1][y1] + pre[x1][y1]

2. LeetCode 1314. 矩阵区域和 (Medium)

   • 训练目标：将二维前缀和应用到具体逻辑中（计算每个元素周围 K 范围内的和）。

---

第三阶段：差分数组 (Difference Array)

核心知识点：

• 关系：差分数组是前缀和数组的“逆运算”。
• 定义：diff[i] = nums[i] - nums[i-1]。
• 作用：主要用于频繁对数组的某个区间进行加减操作。
• 性质：对 nums[i..j] 整体加 val，只需要 diff[i] += val 且 diff[j+1] -= val。最后对 diff 数组求前缀和即可还原出修改后的数组。

必做题目：

1. LeetCode 370. 区间加法 (Medium) （注：这是会员题，非会员可看题解思路）

   • 训练目标：理解差分数组的最基本模版。

2. LeetCode 1109. 航班预订统计 (Medium)

   • 训练目标：完全对应差分数组模版。题目中的“预订”就是对区间 [first, last] 增加座位数。

3. LeetCode 1094. 拼车 (Medium)

   • 训练目标：差分数组的实际应用。
   • 注意：需要注意区间的开闭情况（上车点加，下车点减）。

---

第四阶段：前缀和 + 哈希表 (进阶难点)

核心知识点：

• 痛点：有时候我们需要找“和为 K 的子数组”，如果只用普通前缀和，需要双重循环 $O(N^2)$ 枚举所有子数组。
• 优化：利用公式 preSum[j] - preSum[i] = k 移项得到 preSum[i] = preSum[j] - k。
• 方法：遍历数组计算 preSum[j] 时，去哈希表里查“是否存在一个 preSum[i] 等于 preSum[j] - k”。这可以将复杂度降为 $O(N)$。

必做题目：

1. LeetCode 560. 和为 K 的子数组 (Medium) [重中之重]

   • 训练目标：掌握 HashMap<前缀和, 出现次数> 的套路。这是面试中极高频的考题。

2. LeetCode 523. 连续的子数组和 (Medium)

   • 训练目标：前缀和 + 同余定理。
   • 思路：如果 preSum[j] % k == preSum[i] % k，那么子数组 nums[i...j] 的和就能被 k 整除。Map 存的是 <前缀和余数, 索引>。

3. LeetCode 525. 连续数组 (Medium)

   • 训练目标：数据预处理 + 前缀和。
   • 技巧：题目要求 0 和 1 数量相等。把 0 视作 -1，题目就变成了“求和为 0 的最长子数组”。

4. LeetCode 974. 和可被 K 整除的子数组 (Medium)

   • 训练目标：LeetCode 523 的计数版，结合了 560 和 523 的思路。注意处理负数取模的情况。

---

第五阶段：其他变体

核心知识点：

• 前缀积、前后缀分解。

必做题目：

1. LeetCode 238. 除自身以外数组的乘积 (Medium)
   • 训练目标：不仅有前缀和（积），还有后缀和（积）。
   • 思路：res[i] = prefix[i-1] * suffix[i+1]。

---

总结回顾表

场景	推荐算法	时间复杂度	关键思路
静态数组，频繁查询区间和	前缀和	构造 $O(N)$, 查询 $O(1)$	pre[j] - pre[i]
频繁修改区间，最后查询一次	差分数组	修改 $O(1)$, 还原 $O(N)$	diff[i]+=v, diff[j+1]-=v
求满足特定条件的子数组 (如和为K)	前缀和 + 哈希表	$O(N)$	Map<preSum, count/index>

建议刷题顺序： 先刷 303 -> 304 搞定基本定义； 接着刷 1109 -> 1094 搞定差分思想； 最后集中攻克 560 -> 523 -> 525 掌握哈希表优化技巧（这一块是面试的深水区）。

---

基于 Labuladong 的《双指针技巧秒杀七道数组题目》及相关双指针系列文章，我为你总结了一份循序渐进的题单训练计划。

这份计划将双指针分为三大类：快慢指针、左右指针和中心扩散法，并按照难度和逻辑关联进行了排序。

---

第一阶段：快慢指针 (Fast-Slow Pointers)

核心逻辑：主要解决原地修改数组的问题。

• fast 指针：负责探路，寻找“新”元素或“不需要删除”的元素。
• slow 指针：负责维护“有效数据”的边界，nums[0...slow] 是处理好的结果。

训练题单：

1. LeetCode 26. 删除有序数组中的重复项 (Easy)

   • 训练目标：最基础的快慢指针。理解 fast 遇到不同元素时赋值给 slow。
   • 关键点：数组是有序的，重复元素必相邻。

2. LeetCode 83. 删除排序链表中的重复元素 (Easy)

   • 训练目标：将上一题的逻辑迁移到链表上（虽然是链表，但逻辑完全一致）。

3. LeetCode 27. 移除元素 (Easy)

   • 训练目标：不依赖排序。fast 遇到“非目标值”时赋值给 slow。
   • 关键点：理解题目要求的“原地修改”。

4. LeetCode 283. 移动零 (Easy)

   • 训练目标：相当于第 27 题的变种（移除 0），最后把 slow 之后的部分全部置为 0。

---

第二阶段：左右指针 (Left-Right Pointers) —— 基础篇

核心逻辑：主要解决有序数组搜索或数组翻转问题。

• left 指向 0，right 指向 n-1。
• 根据题目逻辑，两个指针向中间逼近 (left++, right--)。

训练题单：

1. LeetCode 167. 两数之和 II - 输入有序数组 (Medium)

   • 训练目标：理解利用有序特性进行二分逼近。
   • 逻辑：sum > target 则 right--，sum < target 则 left++。

2. LeetCode 344. 反转字符串 (Easy)

   • 训练目标：最基础的交换逻辑。
   • 逻辑：swap(s[left], s[right]) 然后双向收缩。

3. LeetCode 977. 有序数组的平方 (Easy)

   • 训练目标：逆向思维。
   • 逻辑：最大值肯定在两端（负数平方可能变很大），从两端向中间比较，把大的填入新数组的末尾。

---

第三阶段：左右指针 —— 回文串与中心扩散

核心逻辑：解决回文串相关问题。

• 回文判断：标准的左右指针向中间收缩。
• 寻找回文：中心扩散法。从中间向两边扩散 (left--, right++)。

训练题单：

1. LeetCode 125. 验证回文串 (Easy)

   • 训练目标：基础的回文判断，结合简单的字符预处理。

2. LeetCode 5. 最长回文子串 (Medium)

   • 训练目标：掌握中心扩散法。
   • 难点：需要处理奇数长度（中心是一个字符）和偶数长度（中心是两个字符）两种情况。

---

第四阶段：左右指针 —— 进阶应用 (n-Sum & 接雨水)

核心逻辑：结合排序和贪心思想，解决更复杂的逻辑。

训练题单：

1. LeetCode 11. 盛最多水的容器 (Medium)

   • 训练目标：理解贪心策略。
   • 逻辑：面积由短板决定。移动长板只可能导致面积减小，只有移动短板才可能变大。

2. LeetCode 15. 三数之和 (Medium)

   • 训练目标：泛化。将 3Sum 转化为“固定一个数 + 2Sum”。
   • 难点：极其繁琐的去重逻辑（Labuladong 重点讲解了如何优雅地去重）。

3. LeetCode 18. 四数之和 (Medium)

   • 训练目标：递归思想/多层循环。固定两个数 + 2Sum，或者递归解决 k-Sum。

4. LeetCode 42. 接雨水 (Hard)

   • 训练目标：双指针的高级应用。
   • 逻辑：理解每一列能装的水取决于 min(l_max, r_max)。通过双指针边走边维护左右最大值，空间复杂度优化到 $O(1)$。

---

第五阶段：滑动窗口 (Sliding Window) —— 双指针的特殊形态

注：虽然也是双指针，但 Labuladong 通常将其作为独立专题讲解，因为有固定的代码模板。

核心逻辑：right 主动扩张，left 被动收缩。维护窗口内的状态。

必练模板题：

1. LeetCode 76. 最小覆盖子串 (Hard) - 最经典的模板题。
2. LeetCode 567. 字符串的排列 (Medium) - 固定长度窗口。
3. LeetCode 438. 找到字符串中所有字母异位词 (Medium) - 同上。
4. LeetCode 3. 无重复字符的最长子串 (Medium) - 最长窗口，收缩条件不同。

---

总结回顾

阶段	关键词	核心操作	典型例题
一	快慢指针	原地修改数组/链表	删除重复项 (LC 26)
二	左右指针 (基础)	二分搜索、翻转	两数之和 II (LC 167)
三	中心扩散	回文串	最长回文子串 (LC 5)
四	左右指针 (进阶)	贪心、去重、k-Sum	三数之和 (LC 15)、接雨水 (LC 42)
五	滑动窗口	窗口扩张与收缩	最小覆盖子串 (LC 76)

建议刷题顺序：按照阶段一到阶段四顺序练习。阶段五（滑动窗口）建议单独作为一个整块时间集中攻克，因为需要背诵和理解模板代码。

---

单调栈题单

单调栈（Monotonic Stack）是 OI 竞赛中一种非常高效的线性数据结构，也是进入提高组必须熟练掌握的“快刀”。它的逻辑简洁，但能将 $O(n^2)$ 的暴力搜索优化至 $O(n)$。

https://mp.weixin.qq.com/s/880vamP6ui77CSOzCXCrhQ

---

第一阶段：模版夯实（理解核心逻辑）

这一阶段的目标是：理解栈内元素为何必须单调，以及什么时候该“弹出”。

1. [基础模版] 下一个更大元素 I (LeetCode 496)

   • 学习重点：掌握单调栈的标准写法。
   • 教练提示：从后往前遍历数组。在纸上画一个栈，如果新来的数比栈顶大，就把栈顶“踢掉”（因为它不再可能是后面数的下一个更大元素了）。这就是**“生存竞争”**逻辑。

2. [下标映射] 每日温度 (LeetCode 739)

   • 学习重点：学会在栈中存储下标而非数值。
   • 教练提示：很多时候题目要的是“距离”（比如几天后），单纯存数值是不够的。存下标 $i$，通过 $A[i]$ 依然能找到数值。

---

第二阶段：结构变体（打破线性思维）

这一阶段的目标是：处理环形或需要“回头看”的情况。

3. [环形处理] 下一个更大元素 II (LeetCode 503)
   • 学习重点：循环数组的处理技巧。
   • 教练提示：在竞赛中处理环形有两种套路：一是“破环成链”（数组复制两份接在一起），二是“模拟遍历”（利用取模运算 % n 遍历两次）。

---

第三阶段：几何与结构建模（NOI 常考模型）

这一阶段是单调栈真正的威力所在。它不再是简单的查找，而是通过寻找“左右边界”来计算面积或体积。

4. [经典必做] 柱状图中最大的矩形 (LeetCode 84 / 洛谷 P1886 变体)

   • 学习重点：寻找左右第一个比自己小的元素。
   • 教练提示：矩形的高度由最矮的那根柱子决定。你需要知道每一根柱子作为“最短高度”时，向左向右最远能延伸到哪。

5. [经典必做] 接雨水 (LeetCode 42 / 洛谷 P1980 变体)

   • 学习重点：凹槽模型的构建。
   • 教练提示：单调栈在这里维护的是一个“下降序列”。一旦遇到升高的柱子，就形成了一个凹槽，计算横向的盛水量。

---

第四阶段：竞赛实战提高（综合应用）

6. [USACO 经典] Bad Hair Day (洛谷 P2866)

   • 学习重点：贡献法计数。
   • 教练提示：换个思路，不看每头牛能看到多少头，看每头牛能被多少头牛看到。

7. [综合题] 直方图展示 (NOI 导论题)

   • 学习重点：单调栈与贪心的结合。

---

教练的启发式总结：草稿纸上的思考步骤

当你面对一个序列问题，尝试在草稿纸上进行以下推演：

1. 扫描方向：我是该从左往右看（找右边的边界），还是从右往左看（找左边的边界）？
2. 单调性选择：
   • 找更大元素 $\rightarrow$ 维护单调递减栈（一旦遇到大的，弹出，说明找到了）。
   • 找更小元素 $\rightarrow$ 维护单调递增栈。
3. 出栈时机：当 A[i] 破坏了当前的单调性时，被弹出的那些元素，它们的“宿命”就此达成（找到了边界）。
4. 复杂度复核：
   • 时间：每个元素进栈 1 次，出栈 1 次，总复杂度 $O(n)$。
   • 空间：最坏情况下栈的大小为 $O(n)$。

---

读题关键词：什么时候该用单调栈？

在 NOI 读题时，看到以下描述要产生“单调栈”的警觉：

1. “寻找左边/右边第一个比当前数大/小的数”。
2. “寻找以当前位置为最值的最长区间”。
3. “矩形面积/水池深度”（涉及两边界限限制高度的情况）。
4. “距离最近的更高值”。

金牌教练寄语： 单调栈的精髓在于 “及时排除无用信息”。一旦某个元素遇到了比它更优的（更大或更小），它就失去了作为“边界”或“答案”的价值。在草稿纸上模拟这个“排除”过程，你的逻辑就会瞬间清晰。加油！

---

单调队列题单

单调队列不仅是处理“滑动窗口最值”的利器，更是 DP（动态规划）优化中的常客。掌握它，意味着你掌握了将 $O(N^2)$ 复杂度降为 $O(N)$ 的“降维打击”能力。

---

一、 单调队列核心理论：生存逻辑

在单调队列里，有一个非常著名的**“生存逻辑”**：

“如果一个选手比你年轻（位置更靠后），还比你强（数值更大/更小），那你就可以退役了。”

• 性质：队列内的元素从大到小（或从小到大）严格单调。
• 操作：
  1. 入队（Push）：从队尾进入。进入前，将队尾所有比自己“弱”的元素全部踢出（因为它们永远没机会成为最值了）。
  2. 出队（Pop）：当滑动窗口移出了某个元素，且该元素恰好是队首（当前最值）时，才将其弹出。
  3. 查询（Query）：队首永远是当前窗口内的最值。
• 复杂度：每个元素进出各一次，均摊 $O(1)$，总复杂度 $O(N)$。

---

二、 单调队列教程题单

我将题单分为四个等级，请你按顺序在草稿纸上推演每道题的单调性维护过程。

第一阶段：模版与基础（Sliding Window）

1. [LCR 183 / LC 239] 滑动窗口最大值

• 教程意义：这是单调队列的“母体”。学习如何使用 deque 存储下标（存下标是为了方便判断元素是否过期），维护一个单调递减序列。
• 关键词：固定窗口、区间最值。

2. [LC 918] 环形子数组最大和

• 教程意义：引入“前缀和”思想。求子数组和等于 preSum[i] - preSum[j]，要使和最大，即在长度限制内找最小的 preSum[j]。
• 关键词：前缀和、环形处理（倍增数组）。

第二阶段：双端协调与约束（Constraint Subarray）

3. [LC 1438] 绝对差不超过限制的最长连续子数组

• 教程意义：同时维护两个单调队列（一个最大值队列，一个最小值队列）。当 max - min > limit 时，移动左指针并同步更新两个队列。
• 关键词：动态窗口、双队列协同。

第三阶段：DP 优化（NOI 核心考点）

4. [LC 1696] 跳跃游戏 VI

• 教程意义：单调队列优化的入门 DP。状态转移方程为 dp[i] = nums[i] + max(dp[i-k...i-1])。如果直接遍历查找最大值是 $O(N \cdot K)$，用单调队列优化到 $O(N)$。
• 关键词：状态转移、最优子结构查询。

第四阶段：复杂前缀与单调性（Advanced）

5. [LC 862] 和至少为 K 的最短子数组

• 教程意义：这是单调队列最难的一种变体。前缀和不具有单调性（存在负数），需要在入队前和查询时进行双重逻辑判断。
• 关键词：非单调前缀和、最短区间。

---

三、 考场实战：启发式思维提示

当你在读题时，如何一眼识破“单调队列”？请在草稿纸上记录这些关键线索：

1. 读题关键词

• 区间限制：如“长度不超过 $K$”、“在最近 $T$ 秒内”。
• 极值查询：如“最大值”、“最小值”、“最优决策点”。
• 线性增长：决策窗口是随着 $i$ 的增加而向右平移的。

2. 时间复杂度优化建议

• 暴力 $O(N^2)$ 或 $O(NK)$：当你发现你的 DP 方程需要在前面一个范围内找最值时，立刻思考单调队列。
• 常数优化：在 NOI 中，std::deque 比较慢。建议手写数组模拟队列：

  int q[MAXN], head = 0, tail = -1;
  // push: while(head <= tail && val >= q[tail]) tail--; q[++tail] = val;
  // pop: if(head <= tail && q[head] == target) head++;
  

3. 空间复杂度思考过程

• 单调队列本身占用 $O(N)$。
• 注意点：如果题目涉及多层 DP 或多维数组，注意观察单调队列是否可以滚动使用，以节省空间。

---

四、 教练总结

单调队列的精髓在于 “及时止损”：

1. 太老的（过期的）：从队首踢出。
2. 太弱的（没潜力的）：从队尾踢出。

练习建议： 先写出每道题的暴力模拟过程，画出窗口移动时元素进入和离开的轨迹。你会发现，很多元素在还没离开窗口前，就已经因为比新来的元素“弱”而失去了成为最值的可能。把这些“废料”踢出的过程，就是单调队列的优化核心。

去吧，把这 5 道题按照教程思路全部 AC，你的单调队列功底将无懈可击！加油！