4 min read leetcode

739. Daily Temperatures

739. Daily Temperatures
Photo by Markus Spiske / Unsplash

題目連結: 739. Daily Temperatures

題目描述

給定一個整數陣列 temperatures，代表每日的溫度，請根據每日溫度資料，計算在每一天需要等待幾天才能等到更高的溫度。對於無法再等到更高溫度的情況，對應位置的值設為 0。

範例：

  • 輸入：[73, 74, 75, 71, 69, 72, 76, 73]
  • 輸出：[1, 1, 4, 2, 1, 1, 0, 0]

解釋：

  • 第一天，溫度為 73，下一個更高的溫度出現在第二天（74），所以等待 1 天。
  • 第二天，溫度為 74，下一個更高的溫度出現在第三天（75），所以等待 1 天。
  • 第三天，溫度為 75，下一個更高的溫度出現在第七天（76），所以等待 4 天。
  • 以此類推。

限制條件

  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

解題思路

為了有效地解決這個問題，我們需要找到一種能夠在 O(n) 時間內完成的方法。這裡我們採用「單調棧（Monotonic Stack）」的概念來實現。

單調棧方法

  1. 概念：
    • 使用一個棧來保存尚未找到下一個更高溫度的索引。
    • 棧內的溫度值是單調遞減的，因為一旦遇到更高的溫度，我們就會將對應的索引出棧並計算等待天數。
  2. 具體步驟：
    • 初始化一個棧 s 和結果陣列 answer，初始值為 0。
    • 遍歷溫度陣列 temperatures：
      • 當棧不為空，且當前溫度大於棧頂索引對應的溫度時：
        • 從棧頂彈出索引 idx。
        • 計算等待天數：answer[idx] = i - idx。
      • 將當前索引 i 入棧。
    • 最終返回結果陣列 answer。
  3. 示例演算：以輸入 [73, 74, 75, 71, 69, 72, 76, 73] 為例：
    • 第 0 天，溫度為 73，棧為空，將索引 0 入棧。
    • 第 1 天，溫度為 74，74 > 73，彈出索引 0，answer[0] = 1 - 0 = 1，將索引 1 入棧。
    • 第 2 天，溫度為 75，75 > 74，彈出索引 1，answer[1] = 2 - 1 = 1，將索引 2 入棧。
    • 第 3 天，溫度為 71，71 < 75，將索引 3 入棧。
    • 第 4 天，溫度為 69，69 < 71，將索引 4 入棧。
    • 第 5 天，溫度為 72，72 > 69，依次彈出索引 4、3，計算 answer[4] = 5 - 4 = 1，answer[3] = 5 - 3 = 2，將索引 5 入棧。
    • 以此類推。

程式碼

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        const int n = temperatures.size();
        vector<int> ans(n, 0);
        stack<pair<int, int>> s;
        for (int i = 0; i < n; i += 1) {
           while (!s.empty() && temperatures[i] > s.top().first) {
                ans[s.top().second] = i - s.top().second;
                s.pop();
            }
            s.push({ temperatures[i], i });
        }

        return ans;
    }
};

時間與空間複雜度分析

時間複雜度

  • 時間複雜度：O(n)
    • 每個元素最多被壓入棧一次，彈出棧一次，總操作次數與 n 成正比。

詳細分析：

  • 主迴圈遍歷溫度陣列一次，時間為 O(n)。
  • 內部的 while 迴圈在整個運行過程中，總共彈出了 n 次索引（因為每個索引只會被彈出一次），因此內部迴圈的總執行次數為 O(n)。
  • 因此，總時間複雜度為 O(n)。

空間複雜度

  • 空間複雜度：O(n)
    • 需要一個結果陣列 answer，大小為 n。
    • 棧 s 最壞情況下需要存儲 n 個索引。

詳細分析：

  • 結果陣列 answer 大小為 n，為必需的空間。
  • 棧的空間取決於溫度的變化，最壞情況下溫度單調遞減，棧中會存儲所有的索引，因此空間複雜度為 O(n)。

優化方案

反向遍歷法

我們可以嘗試優化空間複雜度，使用反向遍歷的方法，嘗試將空間複雜度降低。

  1. 思路：
    • 從後向前遍歷溫度陣列，對於每一天，我們嘗試找到下一個更高溫度的位置。
    • 使用結果陣列 answer 來記錄等待天數，若 answer[i + 1] 為非零，則可以跳過若干天直接比較。
  2. 實現細節：
    • 初始化結果陣列 answer，初始值為 0。
    • 從倒數第二天開始向前遍歷：
      • 設置索引 j = i + 1。
      • 當 temperatures[i] >= temperatures[j] 且 answer[j] > 0 時，將 j 更新為 j + answer[j]，跳過已經計算過的天數。
      • 若找到更高溫度，則 answer[i] = j - i。

複雜度分析

  • 時間複雜度：最壞情況下為 O(n^2)，因為在最壞情況下內部迴圈可能會遍歷多次。
    • 例如，當溫度序列為嚴格遞減時，每次都無法跳過，需要遍歷剩餘的所有元素。
  • 空間複雜度：O(1)（不計算結果陣列 answer）。
    • 只使用了常數級別的額外變數。

Justin