leetcode 901. 股票价格跨度

看到题目的第一直觉就是栈，一开始抓不住规律。

其实我们每次next找的都是在新元素左边的比新元素大的最后一个数，因此维护一个递减的栈，栈里存数字和数字的下标，每次和栈顶比较， 如果小于的话，那么以这个下标为准，后面的数字都比新元素小。而如果新元素大于栈顶数字，就一直出栈，直到栈顶元素大于新元素。

class StockSpanner {
    private ArrayList<Integer> list;
    private Stack<int[]> num;
    
    public StockSpanner() {
        list = new ArrayList<Integer>();
        num = new Stack<int[]>();
    }
    
    public int next(int price) {
        while(!num.isEmpty() && num.peek()[0] <= price){
            num.pop(); 
        } 
        int res = 1;
        if(num.isEmpty()){
            res =  list.size() + 1;
        }
        else
            res =  list.size() - num.peek()[1];
        list.add(price);
        num.push(new int[]{price,list.size() - 1});
        return res;
    }
}

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