单调栈 leetcode901. 股票价格跨度

单调栈解决 Next Greater Number 一类问题

注意：

单调栈用途不太广泛，只处理一种典型的问题，叫做 Next Greater Element。给你一个数组，返回一个等长的数组，对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> ans(nums.size()); // 存放答案的数组
    stack<int> s;
    for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放
        while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮
            s.pop(); // 矮个起开，反正也被挡着了。。。
        }
        ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个
        s.push(nums[i]); // 进队，接受之后的身高判定吧！
    }
    return ans;
}

1. 从后往前遍历数组，先处理完后面的矮个子，就不用再处理他们了，因为他们已经被前面的高个子挡住了
2. stack的目的是使得stack top保持最高的数，由于是从后往前遍历数组的，所以是从后往前的最高的数。
3. 把stack top与当前的数nums[i]比较，如果还没有当前的数大，那么待会儿把nums[i]入栈的时候，stack当中的数就会被“挡住”，所以直接pop，以后就不用参考了。
4. 最后考虑答案ans，如果s不为empty，那么说明有更高的数，就是s.top，否则没有即为-1

相关习题
901. 股票价格跨度

class StockSpanner {
public:
    stack<int> p;//记录股票价格的单调栈
    stack<int> index;//对应位置，记录日期
    int thisindex;//当前股票对应的日期
    StockSpanner() {
        index.push(0);
        thisindex=0;
    }
    
    int next(int price) {
        thisindex++;//进入新的一天，日期加一
        while(!p.empty() && p.top()<=price){
            p.pop();//把所有的小于等于的全部去掉，构成单调，如果不懂再看看上面的部分
            index.pop();
        }
        int ans=thisindex-index.top();//所求=“当前日期的index”-“当前日期之前的next greater number的index”

        p.push(price);
        index.push(thisindex);

        return ans;

    }
};

1. 为什么想到用单调栈？因为题目之中写到了连续，小于等于，所以就是单调的，就考虑使用单调栈
2. 如何转换为单调栈问题？所求=“当前日期的index”-“当前日期之前的next greater number的index”。因为本日也算上，所以算头又算尾。
3. 首日怎么解决？虚构一个第0天，在初始化的时候index.push(0)，然后让第一天作为day1.

为什么同样的思路，python版本的内存占用反而更小？c++用了80多MB，python只用了近20MB