跳跃游戏、用最少数箭射爆气球、加油站——贪心策略的精妙之处
第17课我们学了贪心的基础：每步选择局部最优。但进阶贪心的难点在于如何定义"局部最优"——不同的贪心策略可能导致完全不同的结果，而错误的策略会遗漏最优解。本课通过三类经典问题，帮你建立贪心的正确直觉。
题目描述：给定一个非负整数数组 nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断是否能到达最后一个下标。
max_reach 表示当前能到达的最远位置。如果当前位置 i > max_reach，说明无法到达位置 i，返回 False。如果 max_reach >= len(nums)-1，返回 True。
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: # 当前位置不可达
return False
max_reach = max(max_reach, i + jump)
if max_reach >= len(nums) - 1:
return True
return True时间复杂度：O(n)，空间复杂度：O(1)
题目描述：给定一个非负整数数组，你最初位于数组的第一个下标。求到达最后一个下标的最少跳跃次数。保证可以到达终点。
cur_end（当前层的右边界）和 next_end（下一层的最远位置），每当到达当前层右边界就 jump+1 并更新边界。
class Solution:
def jump(self, nums: List[int]) -> int:
jumps = 0
cur_end = 0 # 当前跳的右边界
next_end = 0 # 下一跳的最远位置
for i in range(len(nums) - 1): # 不需要跳到最后一格
next_end = max(next_end, i + nums[i])
if i == cur_end: # 到达当前跳的边界
jumps += 1
cur_end = next_end
return jumps时间复杂度：O(n)，空间复杂度：O(1)
i == cur_end 时才 jump，意味着当前跳能覆盖的范围已经全部探索完，必须再跳一次才能继续前进。这就是"层次遍历"的贪心本质——每跳一次都跳到能到达的最远位置。题目描述：一个箭可以沿 x 轴从不同角度射出。给定气球在 x 轴上的水平直径范围，射出一支箭如果穿过气球的直径范围，气球会被射爆。求射爆所有气球所需的最少箭数。
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1]) # 按右端点排序
arrows = 1
arrow_pos = points[0][1]
for start, end in points[1:]:
if start > arrow_pos: # 需要新箭
arrows += 1
arrow_pos = end
return arrows时间复杂度：O(n log n)（排序），空间复杂度：O(1)
核心思想：假设最优解不按贪心策略选择，则可以通过交换得到一个不更差的解，从而证明贪心策略的正确性。
假设贪心解不是最优解，找到第一个不同于最优解的决策点，证明该点选贪心策略不会比选最优策略差，矛盾。
这是最严格的形式化证明，但在面试中通常只需要口头解释即可。
# 常见贪心策略总结
策略 适用场景 经典题目
───────────────────────────────────────────────────
最早结束 区间调度/选最多不重叠 LC 435, 452
最远可达 跳跃/覆盖问题 LC 45, 55
最大/最小 分配/配对问题 LC 135, 621
相邻交换 排序最优 LC 179, 406
局部最优累加 可分解问题 LC 122, 392题目描述：在一条环路上有 n 个加油站，第 i 个加油站有汽油 gas[i] 升，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。求从哪个加油站出发能绕环路一周，返回起始索引。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total = 0
tank = 0
start = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
total += diff
tank += diff
if tank < 0:
start = i + 1
tank = 0
return start if total >= 0 else -1时间复杂度：O(n)，空间复杂度：O(1)