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说明当前层扫描完了必须“跳一次”进入下一层stepsend far把当前层边界推进到下一层最远为什么对因为你在当前这一跳能到的所有位置里选一个点作为落脚点你希望下一跳覆盖最远扫描这一层时取到的最大inums[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 1start i 1开启下一段这是贪心能尽早切就尽早切因为一旦满足条件iend再往右只会让片段变长不会让片段数量更多/更优。class Solution { public ListInteger 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; ListInteger 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; } }