贪心与堆中等2 种解法

#122买卖股票的最佳时机 II

允许完成任意多笔交易但同一时间最多持有一股，求最大总利润。

#数组#贪心#动态规划#股票

解题主线

一段连续上涨区间的首尾差等于其中所有正相邻差之和，因此贪心可以收集每一段上涨收益。

状态机 DP 用“不持股”和“持股”表示每天结束后的最大现金，能直接推广到手续费、冷冻期和交易次数限制。

解法 1：正差值贪心

只要今天价格高于昨天，就把这段相邻涨幅计入利润；所有正涨幅之和等价于每个上涨区间低买高卖。

时间复杂度

O(n)

空间复杂度

O(1)

122. 买卖股票的最佳时机 II · 正差值贪心

java

final class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            profit += Math.max(0, prices[i] - prices[i - 1]);
        }
        return profit;
    }
}

只要今天价格高于昨天，就把这段相邻涨幅计入利润；所有正涨幅之和等价于每个上涨区间低买高卖。

解法 2：两状态动态规划

dp[i][0] 表示第 i 天结束后不持股的最大现金，dp[i][1] 表示持股的最大现金；每天可选择保持状态或买卖。

时间复杂度

O(n)

空间复杂度

O(n)

122. 买卖股票的最佳时机 II · 两状态动态规划

java

final class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

dp[i][0] 表示第 i 天结束后不持股的最大现金，dp[i][1] 表示持股的最大现金；每天可选择保持状态或买卖。

该通用状态机写法空间可压缩到 O(1)，这里保留表格以清晰展示状态转移。

边界与易错点

可以同一天卖出后再买入，但不能同时持有多股；累加正差值并不违反约束。
本题不限交易次数，不能套用第 121 题只记录一笔交易的最低价模型。
DP 的买入转移来自前一天不持股状态，而非初始现金，否则只能完成一笔交易。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/greedy/Q122_maxStockProfit_II.java