901 online stock span

https://leetcode.com/problems/online-stock-span/

mono stack的另一种用法,当前的元素需要立刻知道从自己开始过去有多少元素小于自己,换句话说,需要知道过去第一个大于自己的元素在哪里

class StockSpanner {
    class Node {
        int price;
        int idx;
        public Node(int price, int idx) {
            this.price = price;
            this.idx = idx;
        }
    }
    private Deque<Node> stack;
    private int cnt;

    public StockSpanner() {
        stack = new ArrayDeque<>();
        cnt = 0;
        stack.push(new Node(Integer.MAX_VALUE, cnt));
    }
    
    public int next(int price) {
        cnt++;
        while (stack.peek().price <= price) {
            stack.pop();
        }
        int idx = stack.peek().idx;
        stack.push(new Node(price, cnt));
        return cnt - idx;
    }
}

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

Last updated