901. Online Stock Span

901. Online Stock Span

題意

給定一組陣列的數字代表股價，找出每個 index 的 span

• span 代表過去股價低於或等於今天的天數

• 實作一個 class StockSpanner

  • int next(int price)，會不斷給當天的股價，並回傳 span

限制

• 1 <= price <= 10^5

• At most 104 calls will be made to next.

思考

• 維護一個 monotonic stack

  • 當遇到一個新的股價時，將 stack 中所有小於等於這個新股價的元素彈出，保證 stack top 的股價始終是直到當前未被彈出的最低股價

  • 當接收到新的股價時，stack 如果為空，表示當前的股價是迄今為止觀察到的最高價，因此其跨度就是從股市開市到今天的全部天數

  • 如果 stack 不為空，stack top（股價及索引天數）就代表在不超過當天股價的前提下，可以追溯到的最近的一天。這時，當天的index減去 top 的 index 即得到當天的 span

  • 每計算完一天的跨度後，將當天的股價與對應的天數作為一對元素 push 到 stack 中，這樣可以保證 stack 中始終儲存著所有還未被新的更高股價更新覆蓋的歷史股價資料

Solution

class StockSpanner {
    stack<pair<int, int>> s;
    int day = -1;
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        day += 1;
        if (s.empty()) {
            s.push({ price, day });
            return 1;
        }

        while (!s.empty() && s.top().first <= price) {
            s.pop();
        }
        if (s.empty()) {
            s.push({ price, day });
            return day + 1;
        }

        int diff = day - s.top().second;
        s.push({ price, day });
        return diff;
    }
};

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