langShift贪心算法（题单顺序）
热题 100 - 贪心算法分组（按题单顺序）：121 / 55 / 45 / 763
本页包含题单「贪心算法」分组的全部题目，顺序与 list.json 保持一致。
贪心题统一“自检清单”（点击展开）
- 你在每一步做的局部选择是什么？（例如：当前最小买入价、当前能覆盖到的最远位置、当前段的最远右边界）
- 为什么“局部最优 ⇒ 全局最优”？ 常见证明方式：不变量、交换论证（exchange argument）、单调性剪枝。
- 什么时候贪心不适用？ 一旦局部选择会影响未来多种分支且无法用不变量锁死，往往要转 DP/图搜索。
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 1050 <= prices[i] <= 104
最优解（一次遍历：维护历史最低价）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 这题就是在问：选一个买入日 i、一个卖出日 j（j>i），最大化
prices[j]-prices[i]。 - 朴素做法：枚举 i、j，(O(n^2))。
- 关键推理：卖出当天的最佳买入价一定是“它之前出现过的最低价”。
- 你每天都可以把“到今天为止的最低价”记住：
minPrice。 - 今天如果卖出，利润就是
prices[t] - minPrice。 - 一边扫一边更新最大利润即可。
- 你每天都可以把“到今天为止的最低价”记住：
- 这就是贪心：每一天都做局部最优的“最低买入价更新”，最终得到全局最优利润。
类似题目（前缀最值：维护历史最小/最大）
minSoFar = +inffor x in arr:ans = max(ans, x - minSoFar)minSoFar = min(minSoFar, x)
55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4] 输出：false 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 1040 <= nums[i] <= 105
最优解（贪心：维护能到达的最远下标）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：从 0 出发，每个位置 i 最多跳
nums[i]步，问能不能到最后。 - 关键推理：你不需要知道“怎么跳”，只需要知道“最远能覆盖到哪”。
- 设
far表示目前为止能到达的最远下标。 - 扫描到位置 i 时：
- 如果
i > far，说明你连 i 都到不了，后面更到不了 → false。 - 否则你可以从 i 再扩展覆盖：
far = max(far, i + nums[i])。
- 如果
- 一旦
far覆盖到末尾，就一定可达。
- 设
- 这就是贪心：每一步都把“覆盖范围”扩到最大，不回头、不枚举路径。
类似题目（区间覆盖：维护 farthest reach）
for i:if i > far: failfar = max(far, i + step[i])
45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
0 <= j <= nums[i]且i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000- 题目保证可以到达
n - 1
最优解（贪心分层：每层代表一次跳跃）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 和 55 的区别：55 只问能不能到，45 要最少跳几次。
- 关键推理：把跳跃看成 BFS 的“层”（但用贪心实现）：
- 第 0 次跳能覆盖
[0..end]。 - 在这段覆盖范围里，你可以选择任意一个点作为落脚点，再跳一次。
- 这一层里最好的选择，一定是让下一层覆盖的最远边界最大：
farthest = max(i + nums[i])。
- 第 0 次跳能覆盖
- 为什么 i==end 时 steps++？
- 说明你已经扫描完了“当前这一跳能覆盖的所有位置”，必须进行下一跳了。
- 把
end更新成farthest，相当于进入下一层。
- 这就是贪心：每一跳都把“下一跳能覆盖的最远边界”做到最大，保证跳数最少。
类似题目（分层贪心：currentEnd / farthest）
for i:farthest = max(farthest, i+step[i])if i==end: steps++; end=farthest
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
提示：
1 <= s.length <= 500s仅由小写英文字母组成
最优解（贪心：先记每个字符最后出现位置，再尽量扩区间）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：把字符串切成尽可能多段，每个字母只能出现在其中一段里。
- 关键推理：一段的右边界必须至少覆盖这段里所有字符的“最后一次出现位置”：
- 先预处理
last[ch]：每个字符最后出现的下标。 - 从左到右扫：
- 当前字符
s[i]的最后出现位置是last[s[i]]。 - 当前段的右边界
end必须至少到达它：end = max(end, last[s[i]])。
- 当前字符
- 当
i == end时，说明从 start 到 end 之间出现过的所有字符，它们的最后出现位置都 ≤ end。- 换句话说：这段里的字符不会再出现在后面了，段可以安全切开。
- 先预处理
- 为什么这是“最多段”？
- 一旦满足
i==end就立刻切，贪心地尽早结束当前段，才能留下更多空间给后面的段。
- 一旦满足
类似题目（区间扩张：先预处理 last，再遇到字符扩 end）
end = max(end, last[s[i]])if i==end: cut