C++算法之單調棧

C++算法中的單調棧：從入門到實戰指南

大家好！今天我們來聊聊C++算法中一個超級實用的工具——單調棧。別被名字嚇到，它其實很簡單，就像排隊買奶茶一樣：隊伍總是從矮到高（或從高到矮）排得整整齊齊，這樣處理問題時就特別高效。在算法面試里，單調棧是高頻考點，LeetCode上很多難題（比如找“下一個更大元素”或算“柱狀圖最大面積”）都能用它輕松搞定。這篇文章，我會用接地氣的語言，帶大家一步步理解單調棧的原理、C++實現和應用。全程10000字以上，保證干貨滿滿，讀完你就能上手寫代碼！

一、引言：為什么單調棧這么牛？

想象一下，你在超市排隊結賬。如果隊伍亂七八糟，收銀員得花時間找誰先來誰后到，效率賊低。但如果隊伍按身高排好（比如從矮到高），收銀員一眼就能看出順序，處理速度飛快。單調棧就是這個道理：它是個棧（后進先出的數據結構），但里面的元素保持單調遞增或遞減的順序。這樣處理數組問題時，能省下大量時間。

在C++算法中，單調棧為啥重要？首先，它能把時間復雜度從$O(n^2)$降到$O(n)$，空間復雜度也常是$O(n)$，這在處理大數據時救命啊！其次，接地氣地說，它就像你的“算法瑞士軍刀”——專治各種“找鄰居元素”的毛病。比如：

找數組中每個元素的下一個更大元素（Next Greater Element）。
算柱狀圖中最大矩形面積（LeetCode經典題）。
優化動態規劃問題，避免重復計算。

別擔心，我會用生活例子貫穿全文。比如，把數組元素想象成排隊的人的身高，單調棧就是智能排隊系統。準備好了嗎？我們開整！

二、單調棧的基本概念：到底是個啥？

單調棧，顧名思義，就是棧內元素保持單調性（monotonic）。分兩種類型：

單調遞增棧：棧中元素從底到頂遞增，就像排隊時從矮到高。數學上，如果棧底元素是$a$，棧頂是$b$，那么$a \leq b$。
單調遞減棧：棧中元素從底到頂遞減，排隊時從高到矮，即$a \geq b$。

為啥要單調？核心是利用單調性快速跳過無效比較。舉個例子，假設數組是[2, 1, 4, 3]，我們要找每個元素的“下一個更大元素”。用單調遞減棧：

遍歷到2：棧空，直接入棧。
遍歷到1：1 < 2（棧頂），入棧（棧：[2,1]）。
遍歷到4：4 > 1（棧頂），彈出1，記錄1的下一個更大是4；4 > 2，彈出2，記錄2的下一個更大是4；棧空，4入棧。
遍歷到3：3 < 4，入棧（棧：[4,3]）。結果：2→4, 1→4, 4→無, 3→無。看，只用一次遍歷就搞定！

數學上，單調棧的單調性可以用不等式描述。對于單調遞增棧，任意兩個元素$s_i$和$s_j$（$i < j$），滿足： $$s_i \leq s_j$$ 類似地，單調遞減棧滿足： $$s_i \geq s_j$$ 這種結構讓查找、插入、刪除操作高效，時間復雜度通常是$O(n)$，因為每個元素只入棧出棧一次。

接地氣理解：把它當成一個“智能過濾器”。數組元素一個個進來，棧自動踢掉不滿足單調性的“弱者”，只留“強者”。這樣，問題就簡化了！

三、單調棧的工作原理：一步步拆解

現在，我們深入看看單調棧怎么工作。我會用找“下一個更大元素”（Next Greater Element）這個經典問題演示，接地氣地說，就是“為每個人找右邊第一個比他高的朋友”。

算法步驟（以單調遞減棧為例）：

初始化：創建一個空棧，用于存放數組索引（不是值，索引更方便）。
遍歷數組：從左到右處理每個元素。
比較與彈出：如果當前元素 > 棧頂元素，說明棧頂元素找到了“下一個更大”（就是當前元素），彈出棧頂并記錄結果。
入棧：當前元素入棧（保持棧的單調遞減）。
收尾：遍歷完后，棧中剩余元素沒有“下一個更大”，記為-1或特定值。

偽代碼更直觀：

function nextGreater(arr):stack = empty stackresult = array of size n, initialized to -1for i from 0 to n-1:while stack not empty and arr[i] > arr[stack.top()]:index = stack.pop()result[index] = arr[i]  // 找到下一個更大stack.push(i)return result

實例演示：數組 [3, 1, 4, 2]

步驟1：i=0, 元素3。棧空，入棧（棧：[0]）。
步驟2：i=1, 元素1。1 < 3（棧頂值），入棧（棧：[0,1]）。
步驟3：i=2, 元素4。4 > 1（棧頂值），彈出索引1，記錄result[1]=4；4 > 3，彈出索引0，記錄result[0]=4；棧空，入棧（棧：[2]）。
步驟4：i=3, 元素2。2 < 4，入棧（棧：[2,3]）。
結束：棧中剩余索引2和3，result[2]=-1, result[3]=-1。結果：[4, 4, -1, -1]。完美！

為什么高效？時間復雜度$O(n)$，因為每個元素只入棧一次、出棧一次。空間復雜度$O(n)$，棧最多存n個元素。

接地氣技巧：想象棧是個“候車室”，元素進來等“更大元素”出現。如果等到了，就離開；否則，一直等下去。單調性保證候車室不會亂。

四、C++實現：手把手教你寫代碼

理論懂了，來點實戰！我用C++實現一個完整的單調棧應用——解決“下一個更大元素”問題。代碼盡量簡潔，加詳細注釋，接地氣解釋。

完整C++代碼

#include <iostream>
#include <vector>
#include <stack>
using namespace std;// 函數：找到數組中每個元素的下一個更大元素
vector<int> nextGreaterElement(vector<int>& nums) {int n = nums.size();vector<int> result(n, -1);  // 初始化結果數組，默認-1表示無更大元素stack<int> st;  // 用棧存索引，保持單調遞減// 遍歷數組for (int i = 0; i < n; i++) {// 當棧不空且當前元素大于棧頂元素時，說明棧頂元素找到了"下一個更大"while (!st.empty() && nums[i] > nums[st.top()]) {int topIndex = st.top();  // 獲取棧頂索引st.pop();  // 彈出棧頂result[topIndex] = nums[i];  // 記錄結果}st.push(i);  // 當前元素入棧（索引）}return result;
}int main() {// 測試用例vector<int> arr = {3, 1, 4, 2};vector<int> result = nextGreaterElement(arr);// 輸出結果cout << "原數組: ";for (int num : arr) cout << num << " ";cout << "\n下一個更大元素: ";for (int res : result) cout << res << " ";return 0;
}

代碼詳解（接地氣版）

頭文件：#include <stack> 引入棧，#include <vector> 用動態數組。
nextGreaterElement函數：
- vector<int> result(n, -1): 創建結果數組，初始-1（沒找到更大元素）。
- stack<int> st: 棧存索引，不是值。為啥？因為索引能定位元素，值比較時直接用nums[i]。
- 遍歷循環：for (int i = 0; i < n; i++) 逐個處理元素。
- while條件：!st.empty() && nums[i] > nums[st.top()] – 棧不空且當前元素大于棧頂元素？那就彈出棧頂并記錄。
- 入棧：st.push(i) – 當前索引入棧，保持棧的單調遞減。
main函數：測試數組[3,1,4,2]，輸出結果[4,4,-1,-1]。

編譯運行（用g++）：

g++ -o monotonic_stack monotonic_stack.cpp
./monotonic_stack

輸出：

原數組: 3 1 4 2 
下一個更大元素: 4 4 -1 -1

為什么這樣寫？

用索引存棧：避免值重復問題，比如數組有相同元素時。
單調遞減棧：適合找“下一個更大”；如果找“下一個更小”，就用單調遞增棧。
邊界處理：數組為空時，代碼也能處理（n=0，直接返回）。

接地氣調試：加打印語句看棧變化。例如，在while循環里加cout << "彈出索引: " << topIndex << endl;，觀察執行過程。

五、應用場景：單調棧能解決哪些問題？

單調棧不是花架子，它在算法題中超級實用。下面列舉幾個接地氣的經典應用，全部來自LeetCode，我給出問題描述、解法思路和C++代碼片段。

1. LeetCode 496: Next Greater Element I（簡單題）

問題：給定兩個數組nums1和nums2，nums1是nums2的子集。找到nums1中每個元素在nums2中的下一個更大元素。
解法：先用單調棧處理nums2，得到每個元素的下一個更大；然后用哈希表存結果，遍歷nums1查詢。

C++核心代碼：

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> st;unordered_map<int, int> map; // 存nums2中元素的下一個更大for (int i = 0; i < nums2.size(); i++) {while (!st.empty() && nums2[i] > nums2[st.top()]) {map[nums2[st.top()]] = nums2[i];st.pop();}st.push(i);}// 處理nums1vector<int> result;for (int num : nums1) {result.push_back(map.count(num) ? map[num] : -1);}return result;
}

2. LeetCode 503: Next Greater Element II（數組循環）

問題：數組是環形的，找每個元素的下一個更大（循環查找）。
解法：把數組拉直成兩倍長度，再用單調棧。例如，數組[1,2,1]變成[1,2,1,1,2,1]。

C++核心代碼：

vector<int> nextGreaterElements(vector<int>& nums) {int n = nums.size();vector<int> result(n, -1);stack<int> st;// 遍歷兩遍數組for (int i = 0; i < 2 * n; i++) {int num = nums[i % n]; // 循環索引while (!st.empty() && num > nums[st.top()]) {result[st.top()] = num;st.pop();}if (i < n) st.push(i); // 只存第一遍的索引}return result;
}

3. LeetCode 84: Largest Rectangle in Histogram（難題，柱狀圖最大矩形）

問題：給定柱狀圖的高度數組，求最大矩形面積。
解法：用單調遞增棧。遍歷每個柱子，棧存索引；當當前柱子高度 < 棧頂時，彈出棧頂并計算以它為高的矩形面積。

C++核心代碼：

int largestRectangleArea(vector<int>& heights) {stack<int> st;int maxArea = 0;heights.push_back(0); // 加哨兵值，處理剩余棧for (int i = 0; i < heights.size(); i++) {while (!st.empty() && heights[i] < heights[st.top()]) {int h = heights[st.top()]; // 當前高度st.pop();int width = st.empty() ? i : (i - st.top() - 1); // 計算寬度maxArea = max(maxArea, h * width);}st.push(i);}return maxArea;
}

其他應用

雨水收集問題（LeetCode 42）：用單調棧算每個位置的積水。
每日溫度（LeetCode 739）：找需要等幾天才有更高溫度。
最大矩形（LeetCode 85）：二維矩陣中找最大矩形，結合單調棧。

接地氣總結：單調棧專治“找左鄰居右鄰居”的病。記住口訣：單調棧，順序排；遇大彈出，遇小入棧；一次遍歷，效率賊高！

六、實例分析：柱狀圖最大矩形詳解

我們挑LeetCode 84題（柱狀圖最大矩形）深入分析，因為它是單調棧的招牌應用。接地氣地說，就是“在高低不平的柱子里，找出能畫出的最大長方形”。

問題描述

給定一個整數數組heights，表示柱狀圖的高度。例如，heights = [2,1,5,6,2,3]，柱狀圖如下：

      ____| ||  | |__
__ |  | |  |
| || || || | 
------------2 1 5 6 2 3

求最大矩形面積（上圖最大是10，來自高度5和6的柱子）。

單調棧解法思路

用單調遞增棧（棧底到頂高度遞增）：

遍歷柱子：每個柱子嘗試入棧。
維護單調性：如果當前柱子高度 < 棧頂高度，說明棧頂柱子找到了右邊界（當前索引），彈出棧頂。
計算面積：彈出時，以彈出柱子的高度為矩形高，寬度是右邊界減左邊界（左邊界是棧新頂索引）。
哨兵技巧：在數組末尾加高度0的柱子，強制彈出所有棧中元素。

分步圖解（以heights = [2,1,5,6,2,3]為例）

步驟0：加哨兵，heights變成[2,1,5,6,2,3,0]。
i=0: 高度2，棧空，入棧（棧：[0]）。
i=1: 高度1 < 2（棧頂），彈出索引0：
- 高度h=2，棧空，寬度= i - 0 = 1（左邊界是-1？實際用i=1），面積=2*1=2。
- 入棧1（棧：[1]）。
i=2: 高度5 > 1，入棧（棧：[1,2]）。
i=3: 高度6 > 5，入棧（棧：[1,2,3]）。
i=4: 高度2 < 6，彈出索引3：
- h=6，棧頂索引2（高度5），寬度= i - 2 - 1 = 4-2-1=1，面積=6*1=6。
- 高度2 < 5，彈出索引2：
  - h=5，棧頂索引1（高度1），寬度= i - 1 - 1 = 4-1-1=2，面積=5*2=10（最大）。
- 入棧4（棧：[1,4]）。
i=5: 高度3 > 2，入棧（棧：[1,4,5]）。
i=6: 高度0 < 3，彈出索引5：
- h=3，棧頂4（高度2），寬度=6-4-1=1，面積=3*1=3。
- 高度0 < 2，彈出索引4：
  - h=2，棧頂1（高度1），寬度=6-1-1=4，面積=2*4=8。
- 高度0 < 1，彈出索引1：
  - h=1，棧空，寬度=6，面積=1*6=6。
結束：最大面積是10。

C++完整代碼

#include <iostream>
#include <vector>
#include <stack>
using namespace std;int largestRectangleArea(vector<int>& heights) {heights.push_back(0); // 加哨兵值stack<int> st;int maxArea = 0;for (int i = 0; i < heights.size(); i++) {while (!st.empty() && heights[i] < heights[st.top()]) {int h = heights[st.top()];st.pop();int left = st.empty() ? -1 : st.top(); // 左邊界索引int width = i - left - 1; // 寬度計算maxArea = max(maxArea, h * width);}st.push(i);}return maxArea;
}int main() {vector<int> heights = {2,1,5,6,2,3};cout << "最大矩形面積: " << largestRectangleArea(heights) << endl; // 輸出10return 0;
}

為什么高效？

時間復雜度$O(n)$：每個柱子只處理一次。
空間復雜度$O(n)$：棧最多存n個索引。
接地氣提示：加哨兵（末尾0）是關鍵，確保所有柱子都被彈出計算。

練習：自己畫圖模擬過程，加深理解！

七、單調棧的優缺點：什么場合用？什么場合別用？

單調棧不是萬能的，我們來客觀看看它的好壞，接地氣評價。

優點

高效省時：時間復雜度常是$O(n)$，比暴力法$O(n^2)$快得多。比如找下一個更大元素，暴力法要雙重循環，單調棧一次遍歷搞定。
代碼簡潔：C++實現通常20行以內，邏輯清晰。
應用廣泛：特別適合“基于鄰居元素”的問題，如LeetCode題、面試考點。
空間可控：空間復雜度$O(n)$，棧大小不超過數組長度。

接地氣說：它像“智能導航”，幫你快速找到方向，避免繞彎路。

缺點

適用場景有限：只適合單調性問題。如果問題不涉及元素順序（如求和、排序），就別硬套。
調試麻煩：棧操作容易出錯，比如索引邊界處理不當（左邊界計算）。
理解門檻：初學者可能覺得抽象，需要多練習。
變體復雜：如單調隊列（Monotonic Queue），進階時更難。

使用建議

推薦用：找下一個更大/更小元素、柱狀圖面積、雨水問題等。
不推薦用：動態規劃優化不直接相關時，或問題無單調性。
接地氣口訣：鄰居順序找單調，棧來幫忙快又好；若非此類別硬套，省時省力效率高。

八、進階話題：單調隊列和其他變體

單調棧只是入門，算法世界里還有更強大的工具。比如單調隊列（Monotonic Queue），它能處理滑動窗口問題。接地氣解釋：單調棧是“單點過濾”，單調隊列是“窗口過濾”。

單調隊列簡介

定義：隊列中元素保持單調性，常用于求滑動窗口最大值/最小值。
例子：LeetCode 239: Sliding Window Maximum。

C++實現片段：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq; // 雙端隊列存索引vector<int> result;for (int i = 0; i < nums.size(); i++) {// 移除超出窗口的元素if (!dq.empty() && dq.front() == i - k) dq.pop_front();// 維護單調遞減（隊頭最大）while (!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();dq.push_back(i);if (i >= k - 1) result.push_back(nums[dq.front()]);}return result;
}