739. Daily Temperatures

題目：
一個整數陣列 T，表示每日溫度。對於每一天 i，找出未來第幾天會出現比當天更高的溫度；若不存在則填 0
回傳一個與 T 等長的陣列 ans，ans[i] 為等待的天數

範例：

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

• Example 2:
  Input: temperatures = [30,40,50,60]
  Output: [1,1,1,0]

• Example 3:
  Input: temperatures = [30,60,90]
  Output: [1,1,0]

原先想法：
拿自己跟後面的相比，若比自己小擇加一並移往下一個；反之加一並回傳

結果：
超出時間限制！！！

詢問GPT：

想法：
單調遞減堆疊，堆疊中存放索引，且這些索引對應的溫度從堆疊底到頂是遞減的

• 如果 T[i] <= T[stack.top()]，把 i 推入堆疊（保持遞減性）。
• 如果 T[i] > T[stack.top()]，代表找到了 stack.top() 的下一個更高溫度 → pop 並設定 ans[popIdx] = i - popIdx。持續 pop 直到堆疊空或堆疊頂的溫度 ≥ T[i]，最後把 i push 進去。

優點：每個索引最多被 push/pop 一次 → O(n) 時間、O(n) 空間。

程式碼：

class Solution {
    /**
     * dailyTemperatures
     * Input: int[] T (每天溫度)
     * Output: int[] ans (每天需等幾天才會更暖，沒有則 0)
     */
    public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] ans = new int[n];                    // 預設為 0
        Deque<Integer> stack = new ArrayDeque<>(); // 存放索引，對應溫度單調遞減

        for (int i = 0; i < n; i++) {
            // 當前溫度比堆疊頂端所指的溫度高，代表找到了更暖的一天
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int prevIdx = stack.pop();
                ans[prevIdx] = i - prevIdx; // 等待天數 = 現在索引 - 先前索引
            }
            // 將當前索引放入堆疊（可能是未來更暖天的候選）
            stack.push(i);
        }

        // 剩下在堆疊裡的索引都沒有更高溫，ans 預設為 0
        return ans;
    }
}

實際操作：
T = [73,74,75,71,69,72,76,73]）

Step1:
i=0, T[0]=73 → stack=[] → push 0 → stack=[0]

Step2:
i=1, T[1]=74 → 74>73 → pop 0，ans[0]=1-0=1 → push 1 → stack=[1]

Step3:
i=2, T[2]=75 → 75>74 → pop 1，ans[1]=2-1=1 → push 2 → stack=[2]

Step4:
i=3, T[3]=71 → 71<=75 → push 3 → stack=[2,3]

Step5:
i=4, T[4]=69 → 69<=71 → push 4 → stack=[2,3,4]

Step6:
i=5, T[5]=72 → 72>69 → pop 4, ans[4]=5-4=1; 72>71 → pop 3, ans[3]=5-3=2; 72<=75 → stop; push 5 → stack=[2,5]

Step7:
I=6, T[6]=76 → 76>72 → pop 5, ans[5]=6-5=1; 76>75 → pop 2, ans[2]=6-2=4; push 6 → stack=[6]

Step8:
i=7, T[7]=73 → 73<=76 → push 7 → stack=[6,7]

結果：ans = [1,1,4,2,1,1,0,0]