901. Online Stock Span

題目連結: 901. Online Stock Span

題目描述

設計一個名為 StockSpanner 的類別，對於每一天給出的股票價格，計算該股票當天的跨度（span）。股票的跨度定義為當天及之前連續小於或等於當天價格的最大天數。

具體要求：

• 實作一個類別 StockSpanner，包含以下方法：
  • StockSpanner()：初始化物件。
  • int next(int price)：給出當天的股票價格 price，並返回該股票的當天跨度。

限制條件：

• 1 <= price <= 10^5
• 最多會調用 10^4 次 next 方法。

解題思路

為了高效地計算每一天的股票跨度，我們可以使用單調棧（Monotonic Stack）的概念。單調棧可以在 O(1) 平均時間內找到左側最近的小於或等於當前元素的索引。

主要步驟

1. 初始化：
   • 使用一個棧 s，存儲股票價格與對應的天數索引對（price, day）。
   • 初始化變數 day 為 -1，用於記錄當前是第幾天。
2. 處理每一天的價格：
   • 每次調用 next(price) 方法時：
     • 將 day 增加 1，表示新的一天。
     • 彈出棧內所有價格小於或等於當前價格的元素：
       • 這些元素對應的價格都小於或等於當前價格，因此它們不再影響當前的跨度計算。
     • 計算跨度：
       • 如果棧為空，表示當前價格是目前最高的，跨度為 day + 1（從第 0 天開始計算）。
       • 如果棧不為空，則跨度為 day - s.top().second，其中 s.top().second 是左側最近一個大於當前價格的天數索引。
     • 將當前的價格與天數索引對加入棧中：s.push({price, day})。

為什麼這樣做？

• 棧內元素維護了價格單調遞減的順序：
  • 因為我們在遇到更高價格時，會彈出所有不高於當前價格的元素。
• 跨度計算：
  • 如果棧為空，表示沒有左側更高的價格，跨度為 day + 1。
  • 如果棧不為空，棧頂元素就是左側最近一個高於當前價格的天數索引，跨度為兩者之差。

程式碼

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);
 */

時間與空間複雜度分析

時間複雜度

• 單次 next 方法的時間複雜度：平均為 O(1)。
  • 最壞情況：在單次調用中，while 迴圈可能彈出棧內所有元素，時間為 O(n)，其中 n 為當前天數。
  • 平均情況：由於每個元素最多只會被壓入和彈出棧一次，因此所有調用的總時間為 O(N)，其中 N 為調用次數。
  • 因此，單次調用的平均時間複雜度為 O(1)。
• 總時間複雜度：O(N)，N 為 next 方法被調用的次數（最多 10^4 次）。

空間複雜度

• 空間複雜度：O(N)。
  • 棧 s：在最壞情況下（價格單調遞減），棧中會存儲所有的價格與索引對，因此需要 O(N) 的空間。