Leetcode 連結

暴力解法會使用兩層巢狀迴圈，將每一天的溫度與後面的日子逐一比較，時間複雜度為 O(n²)，在輸入很大時效率不佳。

為了優化，我們可以使用單調堆疊（monotonic stack）來儲存溫度資訊，將時間複雜度降到 O(n)。

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

逐步模擬堆疊過程：
首先初始化一個相同長度、填滿 0 的結果陣列：

res = [0, 0, 0, 0, 0, 0, 0, 0]  
stack = []  // 每個元素為 [索引, 溫度]

  • Index = 0
    Stack: [[0, 73]]
    將當天推入堆疊。

  • Index = 1
    74 > 73 → 彈出 [0, 73]
    res[0] = 1 - 0 = 1
    Stack: [[1, 74]]
    因為今天比堆疊頂端那天更溫暖，所以可以解決等待中的那天（index 0）。
    接著將當天推入堆疊。

  • Index = 2
    75 > 74 → 彈出 [1, 74]
    res[1] = 2 - 1 = 1
    Stack: [[2, 75]]
    同樣地，今天比堆疊頂端更溫暖，所以解決 index 1。
    將當前索引推入堆疊，等待更溫暖的一天。

  • Index = 3
    71 < 75 → 推入 [3, 71]
    Stack: [[2, 75], [3, 71]]
    今天比較冷，無法解決任何先前的日子。
    只需將這一天推入堆疊。

  • Index = 4
    69 < 71 → 推入 [4, 69]
    Stack: [[2, 75], [3, 71], [4, 69]]
    仍然比所有未解決的日子更冷，所以直接推入。

  • Index = 5

    72 > 69 → 彈出 [4, 69]，res[4] = 5 - 4 = 1

    72 > 71 → 彈出 [3, 71]，res[3] = 5 - 3 = 2

    72 < 75 → 推入 [5, 72]

    Stack: [[2, 75], [5, 72]]

…以此類推，直到整個陣列處理完畢。

這個做法確保每個溫度最多只會被推入和彈出堆疊各一次，因此是高效率的 O(n) 解法。

以下是 JAVA 版本

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<int[]> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            int t = temperatures[i];
            while (!stack.isEmpty() && t > stack.peek()[1]) {
                int[] top = stack.pop();
                res[top[0]] = i - top[0];
            }
            stack.push(new int[]{i, t});
        }
        return res;
    }
}