二刷 LeetCode：两道经典贪心题复盘-平芜编程栈

一、LeetCode 45. 跳跃游戏 II

题目回顾

核心思路（正向贪心）

Java 实现代码

二刷反思

二、LeetCode 763. 划分字母区间

题目回顾

核心思路（两次遍历 + 边界扩展）

Java 实现代码

二刷反思

三、贪心算法的通用复盘

二刷贪心算法专题，把两道经典中等题「跳跃游戏 II」和「划分字母区间」重新啃了一遍。比起第一次的懵懵懂懂，这次明显对贪心的核心思想有了更透彻的理解，也想把复盘整理成博客，帮自己沉淀下来，也给同在路上的伙伴们一点参考。

一、LeetCode 45. 跳跃游戏 II

题目回顾

给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。题目保证你一定可以到达终点。

核心思路（正向贪心）

这道题的贪心核心是：不需要知道每一步具体跳到哪个位置，只需要维护当前跳跃能覆盖的区间，在区间内找到下一步能跳得最远的位置，以此减少跳跃次数。

维护三个变量：
- step：记录跳跃次数，初始为 0
- currentEnd：当前这一跳能到达的最远边界
- maxReach：在当前区间内遍历，更新能到达的下一个最远边界
遍历数组（注意不需要遍历到最后一个元素）：
1. 更新maxReach = max(maxReach, i + nums[i])
2. 当遍历到currentEnd时，说明当前区间已经遍历完毕，必须进行下一次跳跃：step++，同时更新currentEnd = maxReach
3. 如果currentEnd已经能到达终点，直接提前结束

Java 实现代码

java

运行

public int jump(int[] nums) { int n = nums.length; if (n <= 1) return 0; int step = 0; int currentEnd = 0; int maxReach = 0; for (int i = 0; i < n - 1; i++) { maxReach = Math.max(maxReach, i + nums[i]); if (i == currentEnd) { step++; currentEnd = maxReach; if (currentEnd >= n - 1) break; } } return step; }

二刷反思

第一次写的时候，很容易陷入「找具体路径」的误区，想着用动态规划记录每个位置的最少跳跃次数，结果写出来的代码又复杂又低效。
这次才真正理解：贪心的精髓是放弃局部最优路径的细节，只保留全局最优的边界信息。时间复杂度直接从 O (n²) 降到了 O (n)，空间复杂度 O (1)，完美符合面试官的期望。
易错点：循环条件是i < n - 1，因为最后一个位置不需要再跳一次，否则会多算一次跳跃次数。

二、LeetCode 763. 划分字母区间

题目回顾

给你一个字符串s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

核心思路（两次遍历 + 边界扩展）

这道题的贪心核心是：先预处理每个字符的最后出现位置，再遍历字符串动态扩展当前片段的边界，当遍历到边界时，就是一个合法的片段。

预处理：第一次遍历字符串，用数组last[26]记录每个小写字母最后一次出现的下标
贪心划分：第二次遍历字符串，维护当前片段的起点start和终点end
- 对于每个字符c，更新end = max(end, last[c - 'a'])
- 当i == end时，说明当前片段已经包含了所有出现过的字符，记录片段长度end - start + 1，并更新start = i + 1

Java 实现代码

java

运行

public List<Integer> partitionLabels(String s) { List<Integer> res = new ArrayList<>(); int[] last = new int[26]; int n = s.length(); // 预处理每个字符的最后出现位置 for (int i = 0; i < n; i++) { last[s.charAt(i) - 'a'] = i; } int start = 0; int end = 0; for (int i = 0; i < n; i++) { end = Math.max(end, last[s.charAt(i) - 'a']); if (i == end) { res.add(end - start + 1); start = i + 1; } } return res; }