序列推进与双向贪心 (Sequence & Bidirectional Greedy)¶

在数组或字符串的线性序列遍历中，贪心策略通常以“动态边界推进”或“双向解耦扫描”的形式呈现。

这类问题不要求事先排序，而是通过在单次或双向遍历中维护局部不变式，以极低的时间复杂度（通常为 \(\mathcal{O}(N)\)）解决看似需要搜索或动态规划的问题。

1. 核心模型与算法架构¶

1.1 动态最远覆盖边界推进 (Reachability Greedy)¶

在跳跃游戏模型中，我们关注的核心不是“究竟从哪一步跳过来”，而是“当前步数内所能覆盖的最远右端点”。

下标:      0   1   2   3   4   5
跳跃力:   [2,  3,  1,  1,  4,  0]
i = 0:    max_reach = 0 + 2 = 2
i = 1:    max_reach = max(2, 1 + 3) = 4
i = 2:    max_reach = max(4, 2 + 1) = 4
... 边界单向拓宽

可达性判定（Jump Game I）：若当前遍历下标 \(i > max\_reach\)，说明位置 \(i\) 根本不可达，直接返回 false；否则更新 \(max\_reach = \max(max\_reach, i + nums[i])\)；
最少步数统计（Jump Game II）：维护 curr_end（当前步数能达到的最远边界）与 max_reach（下一步所能达到的最远边界）。当下标到达 curr_end 时，步数被迫递增 1，并将 curr_end 更新为 max_reach。

1.2 双向约束解耦扫描 (Bidirectional Scanning)¶

当序列中每个位置的状态同时受到左侧邻居与右侧邻居的双重约束时（例如分发糖果问题），直接单向遍历往往无法兼顾全局。

解耦哲学：¶

第一遍从左到右扫描：只满足左规则（若 \(A[i] > A[i-1]\) 则 \(ans[i] = ans[i-1] + 1\)）；
第二遍从右到左扫描：只满足右规则（若 \(A[i] > A[i+1]\) 则 \(ans[i] = \max(ans[i], ans[i+1] + 1)\)）；
结论：两次扫描的极大值合并后，同时且完美满足了左右两边的所有约束条件！

2. LeetCode 经典真题精选与深度精析¶

LeetCode 55 - 跳跃游戏 (Jump Game) 中等
提示

最远覆盖边界推进。
- 无需模拟具体跳跃路径，只需维护全局动态变量 max_reach。
- 遍历下标 \(i\)：若 \(i > max\_reach\)，说明当前位置不可达，返回 false；否则更新 max_reach = max(max_reach, i + nums[i])。
- 若 max_reach >= n - 1 可提前返回 true。严格 \(\mathcal{O}(N)\) 时间、\(\mathcal{O}(1)\) 空间。
LeetCode 45 - 跳跃游戏 II (Jump Game II) 中等
提示

分层 BFS 思想的双指针步数跳跃。
- 维护 curr_end（当前跳跃步数内的最远边界）与 max_reach（下一步能探索到的最远边界）。
- 遍历下标 \(0 \le i < n - 1\)：
- 持续更新 max_reach = max(max_reach, i + nums[i])；
- 当 \(i == curr\_end\) 时，步数加 1（steps++），并更新 curr_end = max_reach。
- 时间复杂度 \(\mathcal{O}(N)\)，额外空间 \(\mathcal{O}(1)\)。
LeetCode 134 - 加油站 (Gas Station) 中等
提示

折线最低点法 / 剩余油量前缀和极值点贪心。
- 令净增油量数组 \(diff[i] = gas[i] - cost[i]\)。
- 充要条件一：若 \(\sum diff[i] < 0\)，总耗油量大于总供油量，无论如何不能跑完一圈，必定返回 \(-1\)；
- 充要条件二：若总和 \(\ge 0\)，环上必存在唯一起点。以 0 为基准绘制前缀累积油量折线图，其全局最低点所在下标为 \(k\)，则起点必定是 \((k + 1) \bmod n\)！因为从全局最低点的下一站出发，能保证后续的累积油量始终处于全周期最高峰，绝不跌破零点。
- 时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(1)\)。
LeetCode 135 - 分发糖果 (Candy) 困难
提示

双向约束解耦的两次贪心扫描。
- 详见本文 1.2 节架构分析。
- 初始时全员分配 1 颗糖；
- 从左往右遍历：若 \(rating[i] > rating[i-1]\)，则 \(candy[i] = candy[i-1] + 1\)；
- 从右往左遍历：若 \(rating[i] > rating[i+1]\)，则 \(candy[i] = \max(candy[i], candy[i+1] + 1)\)。
- 两次遍历求和即可。时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(N)\)。
LeetCode 316 - 去除重复字母 (Remove Duplicate Letters) 中等
提示

单调栈 + 字符剩余频次计数贪心。
- 目标：去重且保证返回结果的字典序最小。
- 统计每个字符的总剩余出现次数，并用布尔数组记录字符是否已在栈中。
- 遍历字符 \(c\)：
- 对应频次递减；若 \(c\) 已在栈中，直接跳过；
- 若栈顶字符 \(top > c\) 且栈顶字符在后续字符串中还会再次出现（剩余频次 \(> 0\)），则贪心地将栈顶弹出（因为未来有机会以更小的字典序在后面重新填入）；
- 将 \(c\) 压入栈并标记；
- 时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(|\Sigma|)\)。
LeetCode 402 - 移掉 K 位数字 (Remove K Digits) 中等
提示

单调栈贪心消除高位逆序对。
- 目标：移除 \(k\) 个数字使得剩下的数字最小。
- 核心贪心原则：对于相同位数的数字，高位越小，整体数值越小。
- 维护一个单调递增栈：从左往右遍历数字字符 \(d\)：
- 若当前数字 \(d < \operatorname{top}\) 且仍有移除配额 \(k > 0\)，则贪心地将栈顶弹出（移除高位大数字），并令 \(k--\)；
- 将当前数字压入栈中；
- 若遍历完后 \(k > 0\)，从栈顶截断剩余的 \(k\) 个数；
- 移除前导零（注意特判空栈返回 "0"）。时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(N)\)。
LeetCode 376 - 摆动序列 (Wiggle Subsequence) 中等
提示

波峰波谷贪心计数与单调区间合并。
- 差值在正负之间交替。
- 贪心观察：在连续单调递增或单调递减的一段区间内，只需保留其端点（局部极值点：波峰与波谷），中间的所有过渡点完全是冗余的。
- 维护前一个差值的符号 prev_diff。遍历相邻两数的差值 curr_diff = nums[i] - nums[i - 1]：
- 若出现波峰（curr_diff > 0 && prev_diff <= 0）或波谷（curr_diff < 0 && prev_diff >= 0），则结果长度加 1，并更新 prev_diff = curr_diff；
- 严格 \(\mathcal{O}(N)\) 线性时间、\(\mathcal{O}(1)\) 空间。
LeetCode 738 - 单调递增的数字 (Monotone Increasing Digits) 中等
提示

逆向高位减 1 + 低位全 9 贪心。
- 寻找 \(\le N\) 的最大单调递增整数。
- 从右向左倒序扫描数字：
- 若发现逆序 \(s[i - 1] > s[i]\)（破坏了递增性）：
  - 贪心地将高位减 1（\(s[i - 1]--\)）；
  - 记录标记位置 \(flag = i\)，以便将从该位置开始的所有后续低位全部置为 '9'（因为只有低位填满 9，才能让数值在合法的条件下达到最大值）；
- 将 \(flag\) 之后的所有字符全改为 '9' 并返回。时间复杂度 \(\mathcal{O}(\log_{10} N)\)，空间复杂度 \(\mathcal{O}(\log_{10} N)\)。
LeetCode 860 - 柠檬水找零 (Lemonade Change) 简单
提示

优先消耗大额零钱的灵活度贪心。
- 顾客支付 5、10、20 美元，找零只需维护 5 元和 10 元钞票的数量（20 元不能找零）。
- 遍历账单：
- 收到 5 元：five++；
- 收到 10 元：必须找 1 张 5 元，five--, ten++；
- 收到 20 元：关键贪心：
  - 优先找一张 10 元和一张 5 元（ten--, five--）；
  - 若没有 10 元，再尝试找三张 5 元（five -= 3）；
  - 为什么优先找 10 元？ 因为 5 元的通用性远高于 10 元（既能给 10 元找零，也能给 20 元找零），保留 5 元能极大降低未来找不开的风险！
- 时间复杂度 \(\mathcal{O}(N)\)，空间复杂度 \(\mathcal{O}(1)\)。