901. Online Stock Span - Medium

前往題目

想法

• Stack，但無從下手

思路

1. next()時，預設span為1
2. stack裡如果有<= price的，就pop然後加到當前span直到stack裡的數比當前price還要大。如此一來就可以捨去一些數字，因為span都儲存在後來的數字裡
3. 結束前把新的price以及span推進stack

變成Monotonic decreasing的stack

Code

class StockSpanner {
    Stack<Pair<Integer, Integer>> stack;

    public StockSpanner() {
        // (Price, span)
        // Pair<Integer, Integer> pair = new Pair<>();
        stack = new Stack();
    }
    
    public int next(int price) {
        // Default span
        int span = 1;

        // Compute span
        while (!stack.isEmpty() && stack.peek().getKey() <= price) {
            span += stack.pop().getValue();
        }

        // Push to the stack
        stack.push(new Pair(price, span));

        return span;
    }
}