LeetCode Hot 100——贪心部分
121. 买卖股票的最佳时机
把每天价格当成一条曲线。你想在某天卖出时赚钱最多，就等价于：
对每一天i作为“卖出日”，找它之前出现过的最低价格作为“买入价”。
所以只要一路扫过去，同时维护：
- 到今天为止的最低价
minPrice - 到今天为止的最大利润
maxProfit
当你看到今天价格price：
- 如果今天卖：利润 =
price - minPrice - 更新最大利润
- 顺便更新
minPrice = min(minPrice, price)
class Solution { public int maxProfit(int[] prices) { int minPrice = Integer.MAX_VALUE; int maxProfit = 0; for(int p : prices) { if(p < minPrice) { minPrice = p; } maxProfit = Math.max(maxProfit, p - minPrice); } return maxProfit; } }55. 跳跃游戏
贪心本质：维护“最远可达位置”far
从左到右扫：
far表示：在当前已经能到达的范围内，通过某个点再跳一步，最远能到哪- 如果扫到某个位置
i时发现i > far：说明 这个位置根本到不了，后面更不可能到，直接 false - 否则更新：
far = max(far, i + nums[i]) - 最后如果
far >= n-1就能到终点
class Solution { public boolean canJump(int[] nums) { int far = 0; for(int i = 0;i < nums.length;++i) { if(i > far) { return false; } far = Math.max(far, i + nums[i]); if(far >= nums.length - 1) return true; } return true; } }45. 跳跃游戏 II
核心思路：两段边界 + 一次扫描
维护三个量：
end：当前这一跳能覆盖到的最右边界（这一层的边界）far：在扫描当前层[0..end]的过程中，能拓展到的下一层最远位置steps：跳跃次数
扫描i从 0 到 n-2（最后一个点不需要再跳）：
- 更新下一层最远：
far = max(far, i + nums[i]) - 如果
i == end，说明当前层扫描完了，必须“跳一次”进入下一层： - steps++
end = far（把当前层边界推进到下一层最远）
为什么对？
因为你在当前这一跳能到的所有位置里，选一个点作为落脚点，你希望下一跳覆盖最远；扫描这一层时取到的最大i+nums[i]就是最优的下一层边界。
class Solution { public int jump(int[] nums) { int n = nums.length; int end = 0; // 当前跳的边界 int far = 0; // 下一跳的最远边界 int steps = 0; // 记录步数 for(int i = 0;i < n - 1;++i) { // 注意是小于n-1, 因为到终点不用再跳，无需扫描 far = Math.max(far, i + nums[i]); if(i == end) { steps++; end = far; // 每次跳时吧end更新为上一轮记录的far } } return steps; } }763. 划分字母区间
核心思路：先记录每个字符最后出现的位置
做两步：
Step A：统计last[c]
last[c]= 字符c在字符串中最后出现的下标。
Step B：从左到右扫，动态扩展当前片段的右边界end
- 设当前片段起点
start - 扫描到位置
i，字符是s[i] - 更新
end = max(end, last[s[i]])
意思是：当前片段里出现的所有字符，它们的最后位置都必须被包含进来 - 当
i == end：说明这段已经“封口”了（片段里所有字符的最后一次出现都在片段内），可以切一刀：- 片段长度
end - start + 1 start = i + 1开启下一段
- 片段长度
这是贪心：能尽早切就尽早切，因为一旦满足条件（i==end），再往右只会让片段变长，不会让片段数量更多/更优。
class Solution { public List<Integer> partitionLabels(String s) { 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, end = 0; List<Integer> res = new ArrayList<>(); 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; } }