来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

Contents

1 题目简介

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

输入例子: [7,1,5,3,6,4]。这个例子中第 2 天买入，第 5 天卖出，收益最大为 5。

2 最简单的思路：暴力，但超时

即将所有的情况进行进行遍历，然后维护一个最大收益值。

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

但是此方法的时间复杂度为 $O(n^2)$ 。此代码将会超时。

3 解决方式一：单调栈

3.1 什么是单调栈？

单调栈，就是栈内元素单调递增或单调递减的栈。只对栈顶进行操作。比如，一个栈从栈底到栈顶依次存储的[1 3 5 9]，则该栈是一个单调递增的栈；反之，一个栈从栈底到栈顶依次存储的[9 5 3 1]，则该栈是一个单调递减的栈。

3.2 为什么这道题可以用单调栈来做？

关键点：股票要有收益，卖出的价格一定要高于买入的价格。

因此，对于单调栈，栈底元素是最小的，可以当做买入的价格，而栈顶元素是最大的，当栈顶元素弹出的时候，可以当做卖出的价格（模拟卖出）。因此，弹栈的时候，要维护一个最大收益值（栈顶减去栈顶即可）。

整体思路

（1）判断栈是否为空，如果为空，则返回 0。

（2）对于第一个元素，直接入栈。

（3）对于之后的元素，与栈顶元素进行比较。如果当前元素大于等于栈顶元素，则直接入栈。如果小于栈顶元素，则弹出栈顶，同时计算收益，维护最大收益值；直到当前元素大于栈顶元素，则入栈。

（4）遍历完所有元素后，输出最大收益值。

3.3 模拟过程

以题目中的数据为例子：[7,1,5,3,6,4]

（1）定义一个空的单调栈，一个最大的收益值 max_p=0。

（2）第一个元素为 7，此时栈为空，直接入栈。单调栈=[7]

（3）第二个元素为 1，小于栈顶元素 7，则将栈顶元素 7 弹出栈。弹出之前，栈顶减去栈底为 0，此时 max_p=0。单调栈=[1]

（4）第三个元素为 5，大于等于栈顶元素为 1。因此直接入栈。单调栈=[1,5]

（5）第四个元素为 3，小于栈顶元素 5，则需要将元素 5 弹栈。弹出之前，栈顶减去栈底为 4，4 大于之前的 max_p,因此 max_p 更新为 4。弹出 5 元素后，栈顶为 1，因此将元素 3 压入。单调栈=[1,3]

（6）第五个元素为 6，6 大于栈顶元素 3，直接压入栈。单调栈=[1,3,6]

（7）第六个元素为 4，4 小于栈顶元素 6，则需要弹栈。弹出之前，栈顶减去栈底为 5，5 大于之前的 max_p=4,因此 max_p 更新为 5。弹出 6 元素后，栈顶为 3，4 小于 3，因此将元素 4 压入。单调栈=[1,3,4]

（8）此时所以元素已经遍历完，此时 max_p=5。将 5 结果输出即可。

疑问：有什么遗漏的点么？

如果数据是[1,3,4],则根据模拟流程，三个元素将依次被压入栈，max_p 将不会被更新。

此时，正确的答案应该是 3，而我们得到的结果为 0。

因此，需要加一个哨兵元素。在股票价格的容器的末尾加一个哨兵元素（例如，可以为-1）。使得数据变为[1,3,4,-1]。加上哨兵元素后，遍历到哨兵元素后，需要一次将 4，3，1 弹栈，则 max_p 会被更新，最后得到正确的结果。

3.4 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 如果容器大小为0，则返回0
        if(prices.size() == 0)
            return 0;
        vector<int> v;
        v.push_back(prices[0]);
        // max_p 为最大的收益
        int max_p = 0;
        //哨兵 -1
        prices.push_back(-1);
        for(int j=1; j<prices.size(); j++)
        {
            // 如果当前值大于等于栈顶，则入栈
            if(prices[j]>=v.back())
                v.push_back(prices[j]);
            // 如果当前值小于栈顶，则循环弹栈，直到栈顶小于当前值
            else
            {
                // 记录当前最大收益，记录完后才能弹栈
                max_p = max(max_p, v.back()-v.front());
                while(v.size()>0)
                {
                    if(prices[j]<v.back())
                        v.pop_back();
                    else
                        break;
                }
                // 将当前值入栈
                v.push_back(prices[j]);
            }
        }
        return max_p;
    }
};

此方法的时间复杂度为 $O(n)$ 。

4 解决方式二：动态规划（dp）

4.1 动态规划解题步骤

很明显，这是一个一维的动态规划。

（1）明确 dp[i]，dp[i] 应该表示什么。

（2）根据 dp(i) 和 dp(i-1) 的关系得出状态转移方程。
（3）确定初始值。

4.2 解题过程

根据 4.1 的分析，dp[i]表示前 i 天的最大收入。

确定 dp[i]与 dp[i-1]的关系：如果第 i 天卖出了股票，则收入为(prices[i]-minprice),如果第 i 天没有卖出股票，则收入为 prices[i-1]。因此取这两者的最大值，即为 dp[i]的值。
即： $dp[i]=max(dp[i-1],prices[i]-minprice)$
其中，minprice 为前 i 天股票的最低价。

初始值：dp[0]=0。

4.3 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        vector<int> dp (n,0);
        int minprice = prices[0];

        for(int i=1;i<n;i++)
        {
            if(prices[i]<minprice)
                minprice = prices[i];
            dp[i] = max(dp[i-1], prices[i]-minprice);
        }
        return dp[n-1];
    }

};