买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

一眼看过去，这个题本质就是要求某个数与其右边最大的数的差值，这符合了单调栈的应用场景 当你需要高效率查询某个位置左右两侧比他大（或小）的数的位置的时候，于是我就用单调栈解决了(但是发现题解很多都是 dp，哈哈)。

这也是两道极为经典的单调栈问题，话不多说，我们来看看如何用单调栈解决这个问题。首先我们要明确这个是在一个时间序列上的，因此我们不能简单的用 最大减最小解决问题，这里我们通过典型的一个例子来解决这个问题 eg:[7,1,5,3,6,4]

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

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

（灰色标记为扫描过的） ①：第一步，栈空，扫描的是 7，我们直接入栈。

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

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

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

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

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

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

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

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 = std::max(ans, St.back() - St.front()); \\ 维护最大值
                St.pop_back();
            }
            St.emplace_back(prices[i]);
        }

        return ans;
    }
};