901. 股票价格跨度 (opens new window)

1.跳表遍历

模拟跳表，对于插入的元素price[i]，如果该元素大于上一个元素price[i-1]，那么计算今日价格跨度时，可以直接利用前一日价格跨度。

每一个元素最多被访问一次，时间复杂度O(n)。(当前元素的结果如果被纳入到后一天的股票跨度中，那么当前元素在后续遍历时就永远不会再次被访问)

class StockSpanner {
    List<int[]> list;
    public StockSpanner() {
        list=new ArrayList<>();
    }
    public int next(int price) {
        int level=find(price,list.size()-1);
        list.add(new int[]{price,level});
        return level;
    }
    public int find(int price,int inx){
        if(inx<0) return 1;
        int currPrice=list.get(inx)[0];
        int currInx=list.get(inx)[1];
        if(currPrice<=price){
            int newInx=inx-currInx;
            return currInx+find(price,newInx); 
        }
        return 1;
    }
}

2.单调栈

单调栈真言：及时去掉无用元素，保证元素有序。

本质上和第一种实现方法没有太大区别。

class StockSpanner {
    Stack<int []> stack;
    public StockSpanner() {
        stack=new Stack<>();
    }
    public int next(int price) {
        int level=1;
        while(!stack.isEmpty()){
            int[] peek=stack.peek();
            int currPrice=peek[0];
            int currLevel=peek[1];
            if(price>=currPrice){
                stack.pop();
                level+=currLevel;
            }
            else break;
        }
        stack.push(new int[]{price,level});
        return level;
    }
}