901. 股票价格跨度

kmp的next数组的思想

next[i]表示第i个数左边，第一个比第i个数大的数的下标

vector里对每个数存储其连续字段和price

如果当前的price比前一个数大，则返回1

否则往前遍历next，每次都加v[next[i]].cnt，直到next[i] == -1  或者 v[next[i]].price > price

class StockSpanner {
public:
    struct node{
        int price, cnt;
        node(int price, int cnt):price(price), cnt(cnt){}
    };
    vector<node> v;
    int pre[150010];
    StockSpanner() {
    }
    
    int next(int price) {
        int cnt = 1;
        int i = v.size();
        if(i - 1 == -1)
        {
            v.push_back(node(price, cnt));
            pre[i] = -1;
        }
        else if(v[i - 1].price > price)
        {
            v.push_back(node(price, cnt));
            pre[i] = i - 1;
        }
        else
        {
            int k = i - 1;
            while(k != -1 && v[k].price <= price)
            {
                cnt += v[k].cnt;
                k = pre[k];
            }
            pre[i] = k;
            v.push_back(node(price, cnt));
        }
        return cnt;

    }
};

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