C++ | 单调栈

对于某一天的股票价格 prices[i]
在这天买入能够获得的最大利润
是 prices[i] 之后出现的，比 prices[i] 大且最大的价格，和它的差值
这是一个经典的单调栈的功能

单调栈用法有二：
1.为出栈元素标记数组某一侧，第一个出现的比它大/小的值
2.为入栈元素标记数组某一侧，曾经出现过的比它大/小且最大/小的值

本题属于用法2的状况
我们倒叙遍历数组，维护一个单调递增栈
若 prices[i] >= 栈顶，证明右侧没有比它更大的值，将prices[i]入栈
若 prices[i] < 栈顶，那么在prices[i]买入的最大收益，就是 栈顶-prices[i]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        stack<int> st;
        st.push(INT_MIN);//单调递增栈-哨兵

        int n = prices.size();
        int res = 0;

        for(int i=n-1;i>=0;--i) {
            if(prices[i]>=st.top()) st.push(prices[i]);
            else res = max(res,st.top()-prices[i]);
        }

        return res;
    }
};