0 Basic

1. 贪心是什么？

   每一步都做当前看起来最优的选择，期望最终得到全局最优解

2. 与动态规划的区别：

   • DP：考虑所有子问题的组合，自底向上构建全局最优
   • 贪心：只看当前一步，不回头，不考虑未来

贪心：每个岔路口走看起来最近的路
DP ：先算出所有路的长度，再选最优

贪心快（O(n)），但不是所有问题都适用
DP 慢（O(n²) 或更高），但一定正确

3. 贪心常见策略：

1 买卖股票的最佳时机 | Easy

题目：prices[i] 是第 i 天的价格。只能买一次卖一次(先买后卖),求最大利润;不交易返回0

• [7,1,5,3,6,4] → 5（第 2 天买，第 5 天卖，6-1=5）

思路分析：

• 贪心直觉：我想在之前的最低点买入，在今天卖出
• 遍历价格，维护到目前为止的最低买入价。对于每一天，计算"今天卖出的利润"并更新最大值

踩坑记录：

• 想好初始值设置，一般最低就设置为float("inf")，最高设置为float("-inf")

代码：

 1class Solution:
 2    def maxProfit(self, prices: List[int]) -> int:
 3        min_price = float("inf")
 4        best = 0
 5
 6        for p in prices:
 7            best = max(best, p - min_price)
 8            min_price = min(p, min_price)
 9
10        return best

复杂度：

• 时间 O(n)
• 空间 O(1)

2 跳跃游戏 | Medium

题目： 数组中每个元素代表在该位置可以跳跃的最大长度。判断是否能到达最后一个位置。

• [2,3,1,1,4] → true
• [3,2,1,0,4] → false

思路分析：

• 贪心直觉：不需要关心具体怎么跳，只需要知道"能到的最远位置"。如果最远位置 ≥ 终点，就能到
• 维护一个变量 farthest，表示目前能到达的最远位置。遍历数组，每到一个位置就更新 farthest。如果某个位置超出了 farthest，说明到不了这里

踩坑记录：

• 顺序不能反: 必须先判 i > max_reach 再更新。反过来写的话,在 i 已经不可达的格子上还去更新栏杆,等于凭空传送
• 判死条件是 i > farthest 而不是 i >= farthest:i == farthest 说明恰好踩在栏杆上,合法

代码：

1class Solution:
2    def canJump(self, nums: List[int]) -> bool:
3        farthest = 0
4        for i, num in enumerate(nums):
5            if i > farthest:
6                return False
7            farthest = max(farthest, i + num)
8        return True

复杂度：

• 时间O(n)
• 空间O(1)

3 跳跃游戏 II | Medium

题目：同上,但保证一定能到终点,求最少跳跃次数

思路分析：

• 贪心 + BFS 思想：把每一次跳跃看作 BFS 的一层。当前层能到达的范围是 [当前位置, current_end]，在这个范围内找下一层能到的最远位置 farthest。走到 current_end 时必须跳一次

踩坑记录：

• 为什么循环到 n-1 而不是 n？ 如果已经在最后一个位置，不需要再跳。如果循环到 n，会在已经到达终点时多算一跳

代码：

 1class Solution:
 2    def jump(self, nums: List[int]) -> int:
 3        n = len(nums)
 4        jumps = 0
 5        current_end = 0 # 当前这一跳能覆盖的最远位置
 6        farthest = 0    # 下一跳能到的最远位置
 7
 8        for i in range(n - 1):
 9            farthest = max(farthest, i + nums[i])
10            if i == current_end:
11                jumps += 1
12                current_end = farthest
13
14        return jumps

复杂度：

• 时间 O(n)
• 空间 O(1)

4. 划分字母区间 | Medium

题目： 把字符串划分成尽可能多的片段，使得每个字母最多只出现在一个片段中。返回每个片段的长度

• "ababcbacadefegdehijhklij" → [9, 7, 8]

思路分析：

1. 先预处理每个字母最后一次出现的位置
2. 遍历字符串，维护当前片段的右边界 end（= 当前片段中所有字母的最远出现位置）
3. 当遍历到 i == end 时，说明当前片段的所有字母都已包含在内，可以切割

踩坑记录：

• 段长是 end - start + 1(闭区间),别忘了 +1。
• 切完之后 start = i + 1,end 不需要手动重置:下一轮 end = max(end, last[c]) 里的 end 虽然是旧值,但此时 end == i < i+1,新的 last[c] 一定 ≥ 当前下标,会自然覆盖掉

代码：

 1class Solution:
 2    def partitionLabels(self, s: str) -> List[int]:
 3        last = {c:i for i, c in enumerate(s)}
 4        res = []
 5        start = end = 0
 6
 7        for i, c in enumerate(s):
 8            end = max(end, last[c])
 9            if i == end:
10                res.append(end - start + 1)
11                start = end + 1
12
13        return res

复杂度：

• 时间 O(n)
• 空间 O(1)（字母表大小固定 26）