problem:901. 股票价格跨度

思路：单调栈找每个数左边第一个比他大的数

Accode:

class StockSpanner {
public:
    vector<int> ins;
    stack<int> sta;
    StockSpanner() {

    }
    int next(int price) {
        ins.push_back(price);
        // int ans = 1;
        while(sta.size() && ins[sta.top()]<=price){
            sta.pop();
        }
        if(sta.size()) {
            int top = sta.top();
            // cout <<top<<endl;
            sta.push(ins.size()-1);
            return ins.size()-1-top;  
        }
        sta.push(ins.size()-1);
        return ins.size();
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

时间复杂度:$o(n)$