LeetCode 热题 100-贪心算法

买卖股票的最佳时机

分析

从左到右枚举价格，维护一个它左边元素的最小值的变量，再维护一个答案变量。

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int ans = 0;
        // 枚举所有价格
        for (int price : prices) {
            ans = Math.max(ans, price - minPrice);
            minPrice = Math.min(minPrice, price);
        }

        return ans;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

买卖股票的最佳时机II

动态规划

与上一题的区别是，现在可以购买多支股票，但每天只能持有一支股票。

定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润，dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（i 从 0 开始）。
状态转移方程：
- dp[i][0]：第i天结束后手里没有股票，即可能前一天就没有股票dp[i-1][0]，或者前一天持有股票但是今天出售了，得到利润dp[i-1][1] + prices[i]。两种情况取较大值。
- dp[i][1]：第i天结束后手里持有股票，即可能前一天没有但今天买入dp[i-1][0]-prices[i]，或者前一天就持有股票dp[i-1][1]，两者取较大值。
初始条件：dp[0][0] = 0，dp[0][1] = -prices[0]。
返回结果：dp[n-1][0]，因为全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候 dp[n−1][0] 的收益必然是大于 dp[n−1][1] 的。

class Solution {
    public int maxProfit(int[] prices) {
        // 定义状态
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][1] = -prices[0];
        // 状态转移
        for (int i = 1; i < n; i++) {
            // 第i天没有股票
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            // 第i天持有股票
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        
        return dp[n-1][0];
    }
}

空间优化：可以用两个变量保存前一天没有股票和持有股票的价格。

class Solution {
    public int maxProfit(int[] prices) {
        // 定义状态
        int n = prices.length;
        int dp0 = 0;
        int dp1 = -prices[0];
        // 状态转移
        for (int i = 1; i < n; i++) {
            // 第i天没有股票
            int newDp0 = Math.max(dp0, dp1 + prices[i]);
            // 第i天持有股票
            int newDp1 = Math.max(dp1, dp0 - prices[i]);
            dp0 = newDp0;
            dp1 = newDp1;
        }
        
        return dp0;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

贪心算法

只要是上升趋势的都买，就能使利益最大化。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int ans = 0;
        for (int i = 1; i < n; i++) {
            ans += Math.max(0, prices[i] - prices[i-1]);
        }
        return ans;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

买卖股票的最佳时机III

动态规划

定义状态：buy1、sell1、buy2、sell2
状态转移
- buy1 = max(buy1, -prices[i])；
- sell1 = max(sell1, buy1 + prices[i])；
- buy2 = max(buy2, sell1 - prices[i]);
- sell2 = max(sell2, buy2 + prices[i]);
初始条件：
- buy1 = -prices[0]
- sell1 = 0 表示同一天买入又卖出
- buy2 = -prices[0] 表示同一天买入又卖出又买入
- sell2 = 0 表示同一天买入又卖出又买入又卖出
返回结果：max(0, sell1, sell2)，如果最优的情况对应的是恰好一笔交易，那么它也会因为我们在转移时允许在同一天买入并且卖出这一宽松的条件，从 sell1转移至sell2，因此最终返回sell2即可。

状态更新解释：buy1 是独立的，它记录的是从开始到当前这一天中最低的买入价格。
sell1 的更新是基于 buy1 来计算的，即在历史上最佳买入价格的基础上，计算当前卖出的最大利润。这两者在更新时互不冲突，buy1 和 sell1 是逐步推进的，因此可以顺序更新 buy1 后再更新 sell1。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        // 枚举价格
        for (int i = 1; i < n; i++) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

买卖股票的最佳时机IV

动态规划

利用上一题的思路：

定义状态：dp[j][0]表示第j次交易后不持有股票的最大利润，dp[j][1]表示第j次交易后持有股票的最大利润。
状态转移：注意，j从后向前遍历，可以避免覆盖上一轮的状态。
- dp[j][0] = max(dp[j-1][0], dp[j-1][1] + prices[i])
- dp[j][1] = max(dp[j-1][1], dp[j-1][0] - prices[i])
初始条件：dp[j][0] = 0，dp[j][1] =负无穷.
返回结果：dp[k][0]。

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        
        // dp[j][0] 表示进行 j 次交易后，不持有股票的最大利润
        // dp[j][1] 表示进行 j 次交易后，持有股票的最大利润
        k = Math.min(k, n / 2);
        int[][] dp = new int[k + 1][2];
        
        // 初始化：进行 0 次交易时，不持有股票最大利润为 0，持有股票的最大利润为负无穷
        for (int j = 0; j <= k; j++) {
            dp[j][1] = Integer.MIN_VALUE; // 初始化持有股票的最大利润为负无穷
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = k; j > 0; j--) {
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]); // 不持有股票时的最大利润
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]); // 持有股票时的最大利润
            }
        }
        
        return dp[k][0]; // 返回最大利润，即进行 k 次交易后，不持有股票的最大利润
    }
}

时间复杂度：$O(n \cdot min(n,k))$
空间复杂度：$O(min(n,k))$

跳跃游戏

贪心

从左到右遍历 nums，同时维护能跳到的最远位置 mx，初始值为 0。
如果 i>mx，说明无法跳到 i，返回 false。
否则，用 i+nums[i]更新 mx 的最大值。
如果循环中没有返回 false，那么最后返回 true。

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

时间复杂度：O(n)
空间复杂度：O(1)

也可以在,x >= n-1时直接返回true。

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

跳跃游戏II

反向查找出发位置

我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。

如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。

找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。

class Solution {
    public int jump(int[] nums) {
        int pos = nums.length - 1;  // 初始化位置为最后一个元素
        int steps = 0;  // 跳跃步数
        // 反向查找
        while (pos > 0) {
            for (int i = 0; i < pos; i++) {
                // 找到可以到达pos的最远节点
                if (i + nums[i] >= pos) {
                    pos = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

时间复杂度：$O(n^2)$
空间复杂度：O(1)

正向查找可到达的最大位置

对于每一个位置i来说，所有能跳到的位置都可以作为下一个起跳点。为了尽可能使用少的跳跃次数，就应该使得下一次起跳能达到的位置尽可能远。即每次在可跳范围内选择可以使下一次跳的更远的位置：

维护变量：当前所能达到的最远位置curRight，下一步所能跳到的最远位置nextRight，最少跳跃次数steps。
遍历数组，每次更新第i个位置下一步所能跳到的最远位置nextRight。
如果索引i到达了当前所能达到的最远位置curRight，就让步数+1，并更新当前最远到达的位置为nextRight.
返回跳跃次数。
注意只需要遍历到i=n-2，不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int curRight = 0, nextRight = 0;
        int steps = 0;
        for (int i = 0; i < n - 1; i++) {
            // 更新下一跳最远位置
            nextRight = Math.max(nextRight, i + nums[i]);
            // 更新跳跃次数
            if (i == curRight) {
                steps++;
                curRight = nextRight;
            }
        }
        return steps;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

划分字母区间

贪心

要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

遍历字符串，得到每个字母最后一次出现的下标位置。
从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标 end，初始时 start=end=0。
对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置$end_c$，则当前片段的结束下标一定不会小于$end_c$，因此令 end=max(end,$end_c$)。
当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是 [start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。
重复上述过程，直到遍历完字符串。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        // 找到每个字符结束的位置
        int[] last = new int[26];
        for (int i = 0; i < n; i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        // 从前往后找区间
        List<Integer> ans = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            // 访问到当前区间末
            if (i == end) {
                ans.add(end - start + 1);
                start = end + 1;
            }
        }

        return ans;
    }
}

时间复杂度：O(n)
空间复杂度：O(|Σ∣)，|Σ∣ = 26.

总结

这一部分贪心算法主要是股票问题和合并区间的问题，思路并不好想，以后再多练习。

算法笔记 > 贪心

#leetcode-hot100

LeetCode 热题 100-贪心算法

http://example.com/2024/12/17/posts/hot100-14/

作者

Xuan Yang

发布于

2024年12月17日

许可协议

LeetCode 热题 100-动态规划上一篇

LeetCode 热题 100-堆下一篇