单调栈

题目：

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

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

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

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

题解：

这里我们维护一个单调增的栈 📈，要赚钱嘛，肯定单调增。
首先讲下维护单调栈的 具体思路：

在 pricesprices 数组的末尾加上一个 哨兵👨‍✈️(也就是一个很小的元素，这里设为 0))，就相当于作为股市收盘的标记(后面就清楚他的作用了)
假如栈空或者入栈元素大于栈顶元素，直接入栈
假如入栈元素小于栈顶元素则循环弹栈，直到入栈元素大于栈顶元素或者栈空
在每次弹出的时候，我们拿他与买入的值(也就是栈底)做差，维护一个最大值。
（灰色标记为扫描过的）
①：第一步，栈空，扫描的是 77，我们直接入栈。

image.png

②：第二步，入栈元素为 1，他比栈顶元素小，为了维护这个单调栈，我们把7弹出，又因为他即是栈底又是栈顶所以不需要更新我们的最大值，又因为弹出之后为空，我们将1直接入栈我们直接入栈。

image.png

③：第三步，入栈元素为 5，他比栈顶元素大，我们直接入栈

image.png

④：第四步，入栈元素为 3，他比栈顶元素 5小，我们直接弹栈，并拿他减去栈底元素1(这就是最重要的，模拟了买卖，因为 5 遇上了比它小的 3，因此即使后面遇到更大的元素 C，但是存在 C−3>C−5，因此它已经没用了，计算之后弹出它

image.png

⑤：第五步，入栈元素为 6，比栈顶元素大，入栈。

image.png

⑥：第六步，入栈元素为 4，比栈顶元素 6小，根据我们刚刚的理论，在遇上 4之后，6 的最高利润已经确定了，因为无论后面遇上怎么样的升值，在 4 的时候购买的利润显然更高 所以我们弹出 6，并与栈底(也就是我们买入的价值)做差，并与我们之前维护的最大值进行比较，然后更新。

image.png

⑦：第七步，现在 哨兵👨‍✈️的作用就非常清楚啦，假如没有哨兵，我们单调栈中还有残留的元素没有进行判断(比如 pricesprices 数组单调增的情况下，不加哨兵会出现 max=0 的情况)，因此 哨兵👨‍✈️的作用就是确保单调栈中的每个元素都被进行判定。因此最后的图像应该是这样：

image.png

现在你对于单调栈的理解肯定更深了吧，不妨看看下面的代码↓

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        
        vector<int> St;
        prices.emplace_back(-1); \\ 哨兵👨‍✈️
        for (int i = 0; i < prices.size(); ++ i){
            while (!St.empty() && St.back() > prices[i]){ \\ 维护单调栈📈
                ans = max(ans, St.back() - St.front()); \\ 维护最大值
                St.pop_back();
            }
            St.emplace_back(prices[i]);
        }

        return ans;
    }
};

最后我们来复习下单调栈 📈的作用和应用场景：
单调栈的作用是:用 O(n)O(n) 的时间得知所有位置两边第一个比他大(或小)的数的位置。