最小棧：O(1)時間獲取棧最小值的雙棧解法詳解
引言：為什麼需要“最小棧”？
在常規棧（Stack）數據結構中，我們可以輕鬆實現push（入棧）、pop（出棧）、top（獲取棧頂元素）三個核心操作，且時間複雜度均為O(1)。但在實際開發中，我們經常會遇到一個需求——快速獲取當前棧中的最小值，比如在表達式計算、單調棧相關算法中。
如果直接使用常規棧實現“獲取最小值”功能，最直接的思路是遍歷整個棧查找最小值，此時時間複雜度會退化為O(n)（n為棧中元素個數），在數據量較大時效率極低。因此，我們需要設計一種特殊的棧結構（即“最小棧”），讓getMin（獲取最小值）操作也能達到O(1) 時間複雜度。
核心思路：雙棧協同實現最小棧
要讓getMin操作達到O(1)，關鍵在於“提前記錄最小值”——用一個輔助棧同步存儲主棧中的“當前最小值”，通過雙棧協同確保輔助棧的棧頂始終是主棧的最小值。
雙棧分工
- 主棧（min_stack1）：存儲所有入棧元素，承擔常規棧的
push、pop、top功能。 - 輔助棧（min_stack2）：僅存儲主棧中的“階段性最小值”，棧頂元素始終是當前主棧的最小值。
核心規則（重點！）
輔助棧的操作需要嚴格遵循以下規則，才能保證棧頂始終是最小值：
- 入棧（push）：
- 先將元素壓入主棧；
- 若輔助棧為空，或當前元素小於等於輔助棧頂元素，則將該元素也壓入輔助棧（“小於等於”是為了處理重複最小值的情況，避免漏記）。
- 出棧（pop）：
- 先判斷主棧頂元素是否與輔助棧頂元素相等（若相等，説明當前最小值即將被彈出，輔助棧需同步彈出）；
- 再將主棧頂元素彈出。
- 獲取最小值（getMin）：直接返回輔助棧頂元素（此時棧頂已保證是主棧當前最小值）。
- 獲取棧頂（top）：直接返回主棧頂元素（與常規棧一致）。
代碼實現與逐行解析（C++版）
下面基於題目中的代碼，逐函數拆解實現邏輯，並補充關鍵註釋。
完整代碼
#include <stack>
using namespace std;
class MinStack {
// 主棧：存儲所有元素
stack<int> min_stack1;
// 輔助棧：存儲當前最小值，棧頂始終是主棧的最小值
stack<int> min_stack2;
public:
/** 構造函數：初始化棧（默認構造即可，無需額外操作） */
MinStack() {
// stack容器的默認構造函數已完成初始化，無需手動清空
}
/** 入棧操作：主棧必壓，輔助棧按需壓 */
void push(int x) {
// 1. 元素先壓入主棧
min_stack1.push(x);
// 2. 輔助棧為空 或 當前元素<=輔助棧頂（保證最小值不丟失），則壓入輔助棧
if (min_stack2.empty() || min_stack2.top() >= x) {
min_stack2.push(x);
}
}
/** 出棧操作：主棧必彈，輔助棧按需彈 */
void pop() {
// 1. 若主棧頂等於輔助棧頂（當前最小值要被彈出），輔助棧同步彈出
if (min_stack1.top() == min_stack2.top()) {
min_stack2.pop();
}
// 2. 主棧彈出頂部元素
min_stack1.pop();
}
/** 獲取主棧頂元素 */
int top() {
return min_stack1.top();
}
/** 獲取當前棧的最小值（直接返回輔助棧頂） */
int getMin() {
return min_stack2.top();
}
};
/** 實例化與調用示例 */
// int main() {
// MinStack* obj = new MinStack();
// obj->push(-2); // 主棧：[-2]，輔助棧：[-2]
// obj->push(0); // 主棧：[-2,0]，輔助棧：[-2]（0 > -2，不壓輔助棧）
// obj->push(-3); // 主棧：[-2,0,-3]，輔助棧：[-2,-3]（-3 <= -2，壓輔助棧）
// cout << "當前最小值：" << obj->getMin() << endl; // 輸出 -3
// obj->pop(); // 主棧彈出-3，輔助棧同步彈出-3 → 主棧：[-2,0]，輔助棧：[-2]
// cout << "棧頂元素：" << obj->top() << endl; // 輸出 0
// cout << "當前最小值：" << obj->getMin() << endl; // 輸出 -2
// delete obj; // 釋放內存
// return 0;
// }關鍵細節答疑
- 為什麼輔助棧要存“小於等於”的元素，而不是“小於”？
假設主棧依次入棧2 → 2：
- 若輔助棧只存“小於”的元素：第一次入棧2（輔助棧[2]），第二次入棧2（2不小於輔助棧頂，不存）；
- 當主棧彈出第一個2時，主棧剩餘[2]，但輔助棧已空，此時
getMin會報錯。
因此，“小於等於”能確保重複最小值被同步記錄，避免最小值丟失。
- 出棧時為什麼要先判斷輔助棧，再彈主棧？
若先彈主棧，主棧頂元素已被刪除，無法再與輔助棧頂對比，會導致輔助棧的最小值無法同步更新。
複雜度分析
|
操作
|
時間複雜度
|
空間複雜度
|
|
|
O(1)
|
O(n)
|
|
|
O(1)
|
O(n)
|
|
|
O(1)
|
O(n)
|
|
|
O(1)
|
O(n)
|
- 時間複雜度：所有操作均為棧的基礎操作（
push/pop/top），均為常數時間O(1)。 - 空間複雜度：最壞情況下（主棧元素嚴格遞減，如
5→4→3→2→1），輔助棧需存儲所有元素，空間複雜度為O(n)（n為主棧元素個數）。
拓展思考：單棧解法 vs 雙棧解法
除了雙棧法，還有一種常見的“單棧解法”——用棧存儲“元素值+當前最小值”的鍵值對（pair<int, int>），每次入棧時計算新的最小值（當前元素與棧頂最小值的較小者）。
單棧解法示例代碼
class MinStack {
stack<pair<int, int>> st; // pair<當前元素, 當前棧最小值>
public:
MinStack() {}
void push(int x) {
if (st.empty()) {
st.push({x, x}); // 空棧時，元素本身就是最小值
} else {
// 新最小值 = min(當前元素, 棧頂最小值)
int new_min = min(x, st.top().second);
st.push({x, new_min});
}
}
void pop() {
st.pop(); // 彈出鍵值對，最小值同步更新
}
int top() {
return st.top().first; // 返回當前元素
}
int getMin() {
return st.top().second; // 返回當前最小值
}
};兩種解法對比
|
維度
|
雙棧解法
|
單棧解法
|
|
邏輯直觀性
|
稍複雜（需理解雙棧協同）
|
更直觀（鍵值對綁定關係）
|
|
空間開銷
|
最壞O(n)，最好O(1)（主棧遞增時）
|
固定O(n)（每個元素都帶最小值）
|
|
代碼簡潔度
|
略繁瑣（兩個棧操作）
|
更簡潔（單個棧操作）
|
實際開發中可根據需求選擇：若追求空間最優（主棧遞增場景多），選雙棧法；若追求代碼簡潔和直觀，選單棧法。
總結
最小棧的核心是“用輔助空間換時間”——通過額外的輔助棧（或鍵值對）提前記錄最小值，將getMin操作從O(n)優化到O(1)，同時保證push和pop操作仍為O(1)。
雙棧解法的關鍵在於輔助棧的“按需入棧/出棧”規則（小於等於入棧、相等出棧），只要掌握這一規則，就能輕鬆實現高效的最小棧。建議結合文中的main函數測試用例，手動模擬棧的變化過程，加深對邏輯的理解！