买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

刚开始我考虑的是动态规划，想不出来。在草稿纸上画出了折线图就想到了可以用队列来做，也就是用单调队列找出所有的上升子序列。

维护一个单调队列使得从队尾到队头单调递减。

初始化最大利润ans=0

如果进队元素小于等于队尾，说明这一段上升序列结束，ans+=队尾-队头，并清空队列，将新元素入队。

否则，将新元素入队。

循环结束后再计算一遍ans+=队尾-队头，把最后一段上升子序列加进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        queue<int> q;
        q.push(prices[0]);
        int ans = 0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]<=q.back()){
                ans+=q.back()-q.front();
                while(!q.empty()) q.pop();
            }
            q.push(prices[i]);
        }
        ans+=q.back()-q.front();
        return ans;
    }
};

很明显空间复杂度为O(n)。

可以把一段上升序列等价成多段子序列，比如说第1天买入，第3天卖出可以等价为第1天买入第2天卖出，第2天再买入第3天卖出。

这样只需要维护第i天的价格和第i-1天的价格，把空间复杂度优化到了常数级别。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxp = 0;
        int ans = 0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]>prices[i-1])
                ans+=prices[i]-prices[i-1];
        }
        return ans;
    }
};