看到題目的第一直覺就是棧，一開始抓不住規(guī)律。

其實(shí)我們每次next找的都是在新元素左邊的比新元素大的最后一個數(shù)，因此維護(hù)一個遞減的棧，棧里存數(shù)字和數(shù)字的下標(biāo)，每次和棧頂比較，?如果小于的話，那么以這個下標(biāo)為準(zhǔn)，后面的數(shù)字都比新元素小。而如果新元素大于棧頂數(shù)字，就一直出棧，直到棧頂元素大于新元素。

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);
 */

?