[Monotonic Stack, Medium] Online Stock Span

https://leetcode.com/problems/online-stock-span/description/?envType=study-plan-v2&envId=leetcode-75

처음에 stack을 이용해서 peek()값이 현재 값보다 작거나 같은 동안 pop하도록 했는데,
이건 반쪽짜리다. 답이 될 수 없다.

왜냐면 작거나 같은 동안 pop한 원소들이 사라지고 새 원소가 들어가는데
이걸 토대로 다시 계산해버리면 당연히 틀린 값이 나온다.

그럼 어떻게 해야 하느냐? stack에 넣을 때 단순히 값만 넣는게 아니라 Pair가 필요하다.
해당 시점 가격의 누계를 다시 더해서 원소를 추가해야 한다는 의미다.

즉, 나보다 작거나 같은 값의 누계로 나를 갱신해 나가면 된다.

class StockSpanner {

    // pair: [price, span]
    private Stack<int[]> stack;

    public StockSpanner() {
        stack = new Stack<>();
    }
    
    public int next(int price) {
        int span = 1;
        while (!stack.isEmpty() && stack.peek()[0] <= price) {
            span += stack.pop()[1];
        }
        stack.push(new int[]{ price, span });
        return span;
    }
}