跳到主要内容

贪心算法练习

贪心算法（Greedy）的核心是：通过在每一步都做出局部最优选择，从而期望达到全局最优。考察重点是如何严谨地证明贪心选择的正确性。

121. 买卖股票的最佳时机 (Best Time to Buy and Sell Stock)​

题目描述​

给你一个数组 prices ，其中 prices[i] 是第 i 天该股票的价格。返回你可以从这笔交易中获取的最大利润。 如果不获取任何利润，返回 0 。

解题思路​

遍历价格数组。维护一个 minPrice 变量记录历史最低价。每到一个点，计算当前价减去 minPrice 的利润，更新最大值。

Java 代码实现​

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE, maxRes = 0;
        for (int p : prices) {
            minPrice = Math.min(p, minPrice);
            maxRes = Math.max(maxRes, p - minPrice);
        }
        return maxRes;
    }
}

55. 跳跃游戏 (Jump Game)​

题目描述​

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

解题思路​

维护一个 maxReach 表示目前能跳到的最远位置。如果当前索引 i 大于 maxReach，说明断裂，返回 false。否则更新 maxReach = max(maxReach, i + nums[i])。

Java 代码实现​

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

45. 跳跃游戏 II (Jump Game II)​

题目描述​

使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达。

解题思路​

贪心寻找。记录当前跳跃能覆盖的最远端 curEnd 和下一次能够覆盖的最远端 maxNext。当遍历到 curEnd 时，必须进行一次跳跃，并将 curEnd 更新为 maxNext。

Java 代码实现​

class Solution {
    public int jump(int[] nums) {
        int steps = 0, curEnd = 0, maxNext = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxNext = Math.max(maxNext, i + nums[i]);
            if (i == curEnd) {
                steps++; curEnd = maxNext;
                if (curEnd >= nums.length - 1) break;
            }
        }
        return steps;
    }
}

763. 划分字母区间 (Partition Labels)​

题目描述​

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段长度的列表。

解题思路​

  1. 预先扫描一遍字符串，记录每个字母最后出现的下标。
  2. 再次扫描。维护当前区间的结束点 end（取区间内所有字母最后出现位置的最大值）。
  3. 当遍历到 end 时，说明可以切割出一个区间。

Java 代码实现​

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(i - start + 1); start = i + 1;
            }
        }
        return res;
    }
}