## 901. Online Stock Span
https://leetcode.com/problems/online-stock-span/description/

## Monotonic stack
- Complexity
- Time: O(1) for amortized analysis
- Space: O(N) in worst case if it's decreasing

class StockSpanner {
    stack<pair<int, int>> stk; // { price, span }
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        int span = 1;

        while(!stk.empty() and price >= stk.top().first){
            span += stk.top().second;
            stk.pop();
        }
        stk.push({price, span});

        return span;
    }
};

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