【LeetCode-309】最佳买卖股票时机含冷冻期

问题

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解答1:完整状态机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> hold(n + 1, -prices[0]); // 初始化变了
        vector<int> sold(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            sold[i] = max(sold[i - 1], hold[i - 1] + prices[i - 1]);
            hold[i] = max(hold[i - 1], sold[i - 2] - prices[i - 1]); // i - 1变为i - 2
        }
        return sold[n];
    }
};

重点思路

由于存在一天的冷冻期,持有状态只能从一天前的持有状态或者两天前的未持有状态转移。这也意味着初始化方法会发生改变。由于循环只能从第二天开始,我们需要单独考虑第一天的情况。第一天不可能卖出,则sold[1] = 0,第一天有可能买入,则将hold[1] = -prices[0]

解答2:状态压缩

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int hold = -prices[0]; // 初始化变了
        vector<int> sold(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            sold[i] = max(sold[i - 1], hold + prices[i - 1]);
            hold = max(hold, sold[i - 2] - prices[i - 1]); // i - 1变为i - 2
        }
        return sold[n];
    }
};

重点思路

根据状态转移方程,hold可以压缩为常数变量。

解答3:状态继续压缩

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int hold = -prices[0];
        vector<int> sold(3, 0);
        for (int i = 2; i <= n; i++) {
            sold[i % 3] = max(sold[(i - 1) % 3], hold + prices[i - 1]);
            hold = max(hold, sold[(i - 2) % 3] - prices[i - 1]);
        }
        return sold[n % 3];
    }
};

重点思路

这里可以改进为滚动数组。令冷冻期为k,则此时空间复杂度为O(k)。

上一篇:写上传文件时,将html中的(选择文件) 元素隐藏,并通过其它方式点击触发


下一篇:简单总结nodejs处理tcp连接的核心流程