題目鏈接
每日溫度
題目描述
?
思路解析 ：單調棧
單調棧介紹：
單調棧是一種特殊的棧數據結構，其核心特性是棧內元素始終保持單調遞增或單調遞減的順序。這種特性使其在解決「尋找下一個更大 / 更小元素」「區間最值」等問題時具有極高效率，時間復雜度通常為 O (n)。
一、單調棧的核心特性
1。單調性：棧內元素按照某種規則（遞增或遞減）嚴格排序
- 單調遞增棧：棧頂元素 ≥ 棧底元素（從棧頂到棧底遞增）
- 單調遞減棧：棧頂元素 ≤ 棧底元素（從棧頂到棧底遞減）
2.操作規則：
- 新元素入棧前，先彈出所有破壞單調性的棧頂元素
- 確保入棧后仍保持原有單調性
- 彈出的元素通常能找到「第一個符合條件的元素」
二、典型應用場景
- 尋找數組中每個元素的「下一個更大元素」
- 尋找數組中每個元素的「下一個更小元素」
- 計算柱狀圖中能接多少雨水
- 計算最大矩形面積
- 解決「每日溫度」問題（如前文代碼）
三、工作原理演示?
下面分別用單調遞增棧和單調遞減棧處理數組[1,4,3,5,5,2,3,6]，并展示處理過程。
?1. 單調遞增棧（棧內元素從棧底到棧頂遞增）
核心規則：新元素入棧時，彈出所有小于當前元素的棧頂元素（確保棧的遞增性），再將當前元素入棧。
處理過程（數組索引 0 到 7，元素依次為 1,4,3,5,5,2,3,6）：
| 步驟 | 當前元素 | 棧操作（彈出小于當前元素的棧頂） | 棧狀態（棧底→棧頂） |
| 0 | 1 | 棧空，直接入棧 | [1] |
| 1 | 4 | 4 > 1（棧頂），直接入棧 | [1,4] |
| 2 | 3 | 3 <4（棧頂），彈出 4；3> 1，入棧 | [1,3] |
| 3 | 5 | 5 > 3（棧頂），直接入棧 | [1,3,5] |
| 4 | 5 | 5 = 5（棧頂），直接入棧（保持遞增） | [1,3,5,5] |
| 5 | 2 | 2 <5（棧頂）→彈出 5；2 < 5→彈出 5；2 < 3→彈出 3；2> 1，入棧 | [1,2] |
| 6 | 3 | 3 > 2（棧頂），直接入棧 | [1,2,3] |
| 7 | 6 | 6 > 3（棧頂），直接入棧 | [1,2,3,6] |
?最終棧狀態：[1,2,3,6]（嚴格遞增）
2. 單調遞減棧（棧內元素從棧底到棧頂遞減）
核心規則：新元素入棧時，彈出所有大于當前元素的棧頂元素（確保棧的遞減性），再將當前元素入棧。
處理過程：
| 步驟 | 當前元素 | 棧操作（彈出大于當前元素的棧頂） | 棧狀態（棧底→棧頂） |
| 0 | 1 | 棧空，直接入棧 | [1] |
| 1 | 4 | 4 > 1（棧頂），彈出 1；棧空，入棧 4 | [4] |
| 2 | 3 | 3 < 4（棧頂），直接入棧 | [4,3] |
| 3 | 5 | 5 > 3（棧頂）→彈出 3；5 > 4→彈出 4；棧空，入棧 5 | [5] |
| 4 | 5 | 5 = 5（棧頂），直接入棧（保持遞減） | [5,5] |
| 5 | 2 | 2 < 5（棧頂），直接入棧 | [5,5,2] |
| 6 | 3 | 3 > 2（棧頂）→彈出 2；3 < 5，入棧 | [5,5,3] |
| 7 | 6 | 6 > 3（棧頂）→彈出 3；6 > 5→彈出 5；6 > 5→彈出 5；棧空，入棧 6 | [6] |
?最終棧狀態：[6]（嚴格遞減）
總結
- 單調遞增棧適合尋找「元素右側第一個更小元素」等場景，棧內始終保持 "后入元素更大" 的特性。
- 單調遞減棧適合尋找「元素右側第一個更大元素」等場景，棧內始終保持 "后入元素更小" 的特性。
- 相等元素的處理可根據需求調整（本文保留相等元素以維持單調性）。
題目解析?
?一：從右往左
核心思路詳解
1. 問題轉化
對于數組中的每個元素?temperatures[i]，我們需要找到最小的?j > i?使得?temperatures[j] > temperatures[i]，結果為?j - i；如果不存在這樣的?j，結果為 0。
2. 單調棧的設計
- 棧的作用：存儲溫度數組的索引，且這些索引對應的溫度值從棧頂到棧底是遞增的（單調遞增棧）。
- 為什么用索引：既需要比較溫度值，又需要計算位置差（天數），存儲索引可以同時獲取這兩個信息。
3. 遍歷方向：從后往前
- 從數組末尾開始遍歷，確保處理當前元素?
i?時，其右側的所有元素都已被處理，棧中已保存了右側可能的 “更高溫度” 候選。
4. 關鍵步驟（以當前索引?i?為例）
-
步驟 1：清除無效候選
當棧不為空，且棧頂索引對應的溫度?≤ 當前溫度?temperatures[i]?時，說明棧頂元素不可能是?i?的 “下一個更高溫度”（因為當前溫度更高），將其彈出。
while (!st.empty() && temperatures[i] >= temperatures[st.top()]) {st.pop();
}步驟 2：計算結果
經過步驟 1 后，若棧仍不為空，棧頂索引就是?i?右側第一個比它溫度高的位置，兩者的差就是結果：
if (!st.empty()) {ans[i] = st.top() - i; // 天數差 = 更高溫度位置 - 當前位置
} else {ans[i] = 0; // 沒有更高溫度
}?步驟 3：入棧當前索引
將當前索引?i?壓入棧中，作為其左側元素的 “更高溫度” 候選：
st.push(i);5. 示例理解
以?temperatures = [73, 74, 75, 71, 69, 72, 76, 73]?為例：
- 遍歷到?
i=6（溫度 76）：棧為空，ans[6]=0，棧中壓入 6。 - 遍歷到?
i=5（溫度 72）：棧頂是 6（76>72），ans[5]=6-5=1，棧中壓入 5。 - 遍歷到?
i=4（溫度 69）：棧頂是 5（72>69），ans[4]=5-4=1，棧中壓入 4。 - ... 以此類推，最終得到結果?
[1,1,4,2,1,1,0,0]。
完整代碼：?
?
復雜度分析
時間復雜度：O(n)，其中 n 為 temperatures 的長度。雖然我們寫了個二重循環，但站在每個元素的視角看，這個元素在二重循環中最多入棧出棧各一次，因此循環次數之和是 O(n)，所以時間復雜度是 O(n)。
空間復雜度：O(min(n,U))，其中 U=max(temperatures)?min(temperatures)+1。返回值不計入，僅考慮棧的最大空間消耗。
?二：從左到右
思路類似：
-
問題目標：對于數組中的每個元素?
temperatures[i]，找到下一個比它大的元素的索引?j，計算?j - i?作為結果；若不存在則為 0。 -
核心思路：使用單調棧（單調遞減棧）存儲溫度的索引，棧內元素對應的溫度始終保持遞減順序。通過遍歷數組，對每個溫度?
temperatures[i]：- 若當前溫度 > 棧頂索引對應的溫度，說明棧頂元素的 “下一個更高溫度” 就是當前溫度，計算間隔天數并彈出棧頂。
- 重復上述過程，直到棧空或當前溫度 ≤ 棧頂溫度，再將當前索引入棧。
-
時間復雜度：O (n)，每個元素最多入棧和出棧各一次。
-
空間復雜度：O (n)，棧的最大存儲量為 n（極端情況：溫度單調遞減時，所有元素入棧）。
完整代碼：
?
以?temperatures = [73, 74, 75, 71, 69, 72, 76, 73]?為例：
- 遍歷到 74（索引 1）時，棧頂是 73（索引 0），74>73，故?
ans[0] = 1-0=1，彈出 0，將 1 入棧。 - 遍歷到 75（索引 2）時，棧頂是 74（索引 1），75>74，
ans[1]=2-1=1，彈出 1，將 2 入棧。 - 后續過程類似，最終結果為?
[1,1,4,2,1,1,0,0]。
?
?
