0309. Best Time to Buy and Sell Stock with Cooldown =================================================== 题目信息 -------- :题号: 0309 :难度: Medium :主题: 股票交易、交易状态、冷冻期、最大利润 :原题: `LeetCode 0309 `_ :重点: 可以完成多次交易、同一时间最多持有一股、卖出后的下一天禁止买入 题目重述 -------- 给定数组 ``prices``,其中 ``prices[i]`` 表示第 ``i`` 天的股票价格。可以进行任意多次买入和卖出,每次交易只能持有一股股票,因此必须先卖出当前持股才能再次买入。 卖出股票后的下一天属于冷冻期,不能在该天买入;可以选择什么都不做。返回在整个时间段内能够获得的最大总利润。``prices`` 的长度位于 ``[1, 5000]``,每个价格位于 ``[0, 1000]``。题目不收取交易手续费,也不要求返回具体交易日期。 自建示例 -------- 冷冻期阻止紧接着再次买入: .. code-block:: text 输入:prices = [1, 4, 2, 3, 0, 5] 输出:8 解释:第 0 天以 1 买入、第 1 天以 4 卖出,利润为 3;第 2 天必须冷冻,之后第 4 天以 0 买入、第 5 天以 5 卖出,再获利 5,总利润为 8。 没有获利机会: .. code-block:: text 输入:prices = [6, 4, 2] 输出:0 解释:价格持续下降,选择不交易比任何买卖方案都好。 把每天结束时的持仓状态分开 ---------------------------- 冷冻期的限制只影响“今天能否买入”,所以关键不是记录最后一次交易,而是区分每天结束时所处的状态:``hold`` 表示手里持有股票,``sold`` 表示今天刚卖出,``rest`` 表示不持股且不处于刚卖出的状态。每个状态保存截至当天的最大利润。 第 ``i`` 天结束时,持有股票可以来自昨天继续持有,也可以从昨天的 ``rest`` 状态买入;不能从昨天 ``sold`` 买入,这正是冷冻期约束。今天刚卖出只能由昨天持股卖出;今天处于 ``rest`` 则可以来自昨天继续休息,或昨天已经卖出并度过冷冻期。用上一天的三个值计算新值,再覆盖旧值即可。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int maxProfit(std::vector& prices) { const long long impossible = -(1LL << 60); long long hold = -prices[0]; long long sold = impossible; long long rest = 0; for (int i = 1; i < static_cast(prices.size()); ++i) { long long nextHold = std::max(hold, rest - prices[i]); long long nextSold = hold + prices[i]; long long nextRest = std::max(rest, sold); hold = nextHold; sold = nextSold; rest = nextRest; } return static_cast(std::max(sold, rest)); } }; 代码分析 -------- ``newHold`` 只从旧的 ``rest`` 买入,因此不会把卖出后的第二天误当成可买入日;``newRest`` 接收旧的 ``sold``,表示冷冻期在今天结束。初始第一天不可能已经卖出,所以把 ``sold`` 设为负无穷,避免引入虚假的交易。三种状态只依赖上一天,时间复杂度为 ``O(n)``,额外空间为 ``O(1)``。