局部最优→全局最优，贪心是算法设计中最直觉也最需证明的策略
贪心算法在每一步都选择当前看起来最优的选项，期望局部最优选择能导致全局最优解。贪心的关键不是"贪"，而是证明贪心策略的正确性。不是所有问题都能贪心，但能用贪心的问题往往有优美的解法。
| 维度 | 贪心 | DP |
|---|---|---|
| 决策方式 | 局部最优（不回头） | 穷举所有可能 |
| 正确性 | 需证明（容易错） | 天然正确（定义保证） |
| 时间复杂度 | 通常O(n log n) | 通常O(n^2)或更高 |
| 适用范围 | 窄（需特殊性质） | 宽（有最优子结构即可） |
| 调试难度 | 难（反例不明显） | 易（状态可追踪） |
给定非负整数数组 nums，初始位于下标0，每个元素代表该位置可跳跃的最大步数，判断是否能到达最后一个下标。
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i, n in enumerate(nums):
if i > max_reach: # 到不了位置i
return False
max_reach = max(max_reach, i + n)
return True
# 也可以提前终止
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i, n in enumerate(nums):
if i > max_reach:
return False
max_reach = max(max_reach, i + n)
if max_reach >= len(nums) - 1:
return True
return True时间: O(n) 空间: O(1)
给定非负整数数组，假设总能到达最后一个下标，返回到达终点的最少跳跃次数。
class Solution:
def jump(self, nums: List[int]) -> int:
jumps = 0
cur_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = farthest
return jumps时间: O(n) 空间: O(1)
给定区间集合，返回需要移除的最小区间数，使剩余区间互不重叠。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
count = 0
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] < end: # 重叠
count += 1
else:
end = intervals[i][1]
return count
# 等价写法：求最多能保留多少个
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
keep = 1
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] >= end:
keep += 1
end = intervals[i][1]
return len(intervals) - keep时间: O(n log n)（排序）空间: O(1)
在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：
# 通用解题模板
class Solution:
def solve(self, input_data):
# 1. 边界检查
if not input_data:
return default_value
# 2. 初始化
result = initial_value
state = initial_state
# 3. 主循环
for item in input_data:
state = transition(state, item)
result = max/min/update(result, state)
# 4. 返回结果
return result