題意理解
給定一個整數陣列 temperatures 表示每天的溫度，要求返回一個陣列 answer 用以表示在對應位置，需要等待多少天才能觀測到更高的溫度，如果溫度在這之後都不會升高，則以 0 表示。比如：
temperatures = [73, 74, 75, 71, 69, 72, 76, 73] answer = [1, 1, 4, 2, 1, 1, 0, 0]
觀察以上的範例輸入與輸出：
- 在第
0天時，當天溫度為 73 而下一個更高的溫度為第1天的 74，因此answer[0] = 1。 - 在第
1天時，當天溫度為 74 而下一個更高的溫度為第2天的 75，因此answer[1] = 1。 - 在第
2天時，當天溫度為 75 而下一個更高的溫度為第6天的 76，因此answer[2] = 4。 - 在第
3天時，當天溫度為 71 而下一個更高的溫度為第5天的 72，因此answer[3] = 2。 - ……
由於陣列 temperatures 較大，需要有較佳效率的解決方案。
解法：單調堆疊
思路想法
在本題中，需要 查找當前元素右側第一個比當前元素大的元素，因此可以維護一個 單調堆疊（monotonic stack） 來輔助求解。
單調堆疊（monotonic stack）是一個特殊的堆疊（stack）資料結構，其中元素必須按照單調遞增或單調遞檢的順序排列，適用於查找陣列中每個元素的「下一個更大元素」、「下一個更小元素」、「前一個更大元素」和「前一個更小元素」等場景。
我們需要在遍歷陣列的過程中動態地維護單調堆疊，過程中由於每個元素至多被壓入（push）和彈出（pop）一次，因此其平均的時間複雜度為 \( \mathcal{O}(n) \)。
在本題中，由於我們最終需要根據索引計算得到天數，因此 保存的元素必須為索引值 而非溫度值。具體的操作為：
- 從左到右掃描
temperatures陣列，將當前的索引值i放入堆疊中。 - 對於每一個溫度值
temperatures[i]而言，需要和堆疊頂部索引值對應的溫度temperatures[stack.top()]進行比較。如果待壓入的溫度值temperatures[i]更高，則彈出堆疊頂部元素並更新answer[stack.top()]答案陣列；否則直接將新的索引值壓入即可。
由於題目要求若找不到更高溫度時，需要以 0 表示，因此對於 answer 陣列，可以直接先將所有元素初始化為 0。
範例程式
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] answer = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
return answer;
}
}
在 Java 程式語言中，建議採用更為現代且高效率的 Deque 集合元素，雖然其本身設計是用於實現雙端貯列（double-ended queue, deque）資料結構，但其 API 亦能用於實現堆疊（stack）的功能。因為 Stack 集合元素繼承自 Vector 元素，由於其本身同步的設計，在操作性能上會帶來額外的開銷。
上述提到的「同步」概念，是指在多執行緒環境中，當多個執行緒嘗試同時操作
Vector 時，會需要確保同一時間只有一個執行緒進行操作，以避免數據不一致的問題，但同步機制也會帶來額外的性能開銷，比如上下文切換、加鎖與釋放鎖的操作等。
複雜度分析
- 時間複雜度：\( \mathcal{O} (n) \)，其中 \( n \) 為陣列
temperature的長度。 - 空間複雜度：\( \mathcal{O} (n) \)。
張貼留言