為了你，我變成狼人模樣；

為了你，染上了瘋狂~

stack棧練習

棧

一種先進后出的線性數據結構

具體用法可參考往期文章或者維基介紹i

對應簡易練習

20. 有效的括號 - 力扣（LeetCode）

32. 最長有效括號 - 力扣（LeetCode）

括號的分數

856. 括號的分數 - 力扣（LeetCode）

本題主要是為了計算平衡括號字符串的分數，利用棧模擬并計算分數。遍歷字符串，在遇到右括號時根據最近匹配情況更新分數。

法一：利用棧，遍歷字符處理

左括號 (：壓入新的 0 作為當前層的分數占位符

右括號 )：

• 彈出棧頂值 v（最近未匹配括號計算的分數）
• 分類更新分數：
  • v=0：最近是未匹配的左括號，形成 () 得1分
  • v>0：最近是已匹配括號組，形成 (A) 得 2v 分
• 將計算出的分數累加到新的棧頂（上一層）

利用棧可以記錄每層括號的中間分數，又因為他是先進后出的結構所以可以自動處理嵌套的關系，棧頂始終保存當前層的結果；遍歷完后最終棧頂即為整個字符串的總分；

class Solution {
public:int scoreOfParentheses(string s) {stack<int> st;st.push(0);for (auto c : s) {if (c == '(') {st.push(0);} else {int v=st.top();st.pop();if(v==0)st.top()+=1;elsest.top()+=v<<1;}}return st.top();}
};

法二：利用棧的思想，分層級處理（有點類似于后綴表達式）

仔細觀察，不難發現，題目中給出的字符串可匹配一定是合理的；所以每經歷到一次(就相當于進入了一個新的層級（觸發了嵌套關系）而遇到)就相當于退出了一個層級（結束嵌套）；而遇到一個完整的()就是一個單位1，判斷這個單位1處在那個層級累加到結果中（因為每個單獨的()是相加的關系）即為所求；

這個方法通過維護一個動態乘數 n 來計算分數，核心思想是將嵌套括號轉化為深度相關的乘數累計

初始

• n=1 作為基礎乘數（對應嵌套深度0）（n 表示當前括號所在深度的分數倍率）
• an=0 作為總分累加器

遍歷字符串：

• 左括號 (：
  • 將乘數 n 左移一位（n <<= 1），相當于乘數加倍（進入下一層）
• 右括號 )：
  • 將乘數 n 右移一位（n >>= 1），相當于恢復上層乘數（退出當前層）
  • 判斷：如果當前)與前一個字符形成()：
    • 將當前乘數 n 累加到總分 an 中

class Solution {
public:int scoreOfParentheses(string s) {int n=1,an=0;for(int i=0;i<s.size();i++){if(s[i]=='(')n<<=1;elsen>>=1;if(s[i]==')'&&s[i-1]=='(')an+=n;}return an;}
};

和法一相比時間復雜度差不多（O(n)），都需要遍歷一次字符串；但是空間復雜度從原先的O(n)（棧空間）降低到了O(1)（常數空間）；

---

單調棧

單調棧，你不乘哦

何為單調棧？顧名思義，單調棧即滿足單調性的棧結構。與單調隊列相比，其只在一端進行進出。

將一個元素插入單調棧時，為了維護棧的單調性，需要在保證將該元素插入到棧頂后整個棧滿足單調性的前提下彈出最少的元素。

原理：維護一個棧，保持棧內元素單調遞減。當處理新元素時，彈出所有比它小的元素，這些被彈出的元素與新元素形成一定的關系。

使用場景：適用于需要找到每個元素左邊或右邊第一個比它大或小的元素的問題。

實現步驟：
初始化空棧
對于每個元素：
彈出棧中所有比當前元素小的元素（這些元素能被當前元素看到）
計算當前元素能被棧中剩余元素看到的數量（即棧的大小）
將當前元素壓入棧

while(棧頂元素比入棧元素小或大 && 棧不空)
{棧頂元素彈出
}
元素入棧

---

模板框架

P5788 【模板】單調棧 - 洛谷

最基礎的模板題，需要我們尋找序列中每個元素"下一個更大元素"的位置（下標）

維護單調性使用棧維護"尚未找到下一個更大元素"的下標，保持棧底到棧頂對應的元素值單調遞減，當新元素a[i]比棧頂對應元素大時，說明新元素是棧頂元素的"下一個更大元素"

從左到右遍歷一遍序列

• 若a[i] > 棧頂對應元素 → 彈出棧頂并記錄答案
• 當前下標i入棧（等待后續元素為其尋找更大值）

遍歷結束后棧中剩余的元素（無更大元素），答案默認為0

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e7;
int a[N],an[N];
stack<int> s;
void slove(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(s.size()==0){s.push(i);continue;}if(a[i]>a[s.top()]){while(s.size()&&a[i]>a[s.top()]){an[s.top()]=i;s.pop();}}s.push(i);}for(int i=1;i<=n;i++)cout<<an[i]<<' ';
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

同類型的套用模板的題目還有

739. 每日溫度 - 力扣（LeetCode）

[P2866 [USACO06NOV] Bad Hair Day S - 洛谷](https://www.luogu.com.cn/problem/P2866)

時間復雜度：O ( n )，每個元素最多入棧和出棧一次。
空間復雜度：O ( n )，最壞情況下所有元素都在棧中。

---

小結

單調棧是解決"第一個比當前元素大/小"這類問題的有效工具。本題通過維護一個單調遞增棧，保證了每個元素都能在O(1)均攤時間內找到左邊第一個比它小的數。關鍵在于理解為什么可以安全地彈出那些不會影響后續結果的元素，從而保持棧的單調性。

這種算法思想在很多場景下都有應用，比如計算直方圖的最大矩形面積、求解滑動窗口最大值等問題。掌握單調棧的使用可以大大提高解決這類問題的效率。

---

下一個更大元素 I（單調棧+哈希）

496. 下一個更大元素 I - 力扣（LeetCode）

本題需要為 nums1 中的每個元素在 nums2 中尋找下一個更大的元素（Next Greater Element）。核心思路是利用單調棧高效解決，并結合哈希表存儲結果。

1.遍歷 nums2 時維護一個遞減棧（棧底到棧頂元素遞減）：

當前元素 i 若小于等于棧頂，直接入棧。

當前元素 i 若大于棧頂，則 i 是棧頂元素的下一個更大元素。此時將棧頂彈出并記錄映射 mp[棧頂] = i，直到棧頂不小于 i 或棧空。

結果：棧中最后剩余的元素在 nums2 中無下一個更大元素。

2.哈希表記錄映射

使用 unordered_map<int, int> mp 存儲 nums2 中元素的下一個更大元素。

當元素被彈出棧時，其下一個更大元素被記錄（即觸發彈出操作的元素）。

3.最后處理 nums1 的結果，找到每個對應的i即可

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> a;unordered_map<int,int> mp;stack <int> s;for(auto i:nums2){if(s.size()==0){s.push(i);continue;}while(s.size()&&i>s.top()){mp[s.top()]=i;s.pop();}s.push(i);}for(auto i:nums1){if(mp[i]==0)a.push_back(-1);elsea.push_back(mp[i]);}return a;}
};

---

接雨水

42. 接雨水 - 力扣（LeetCode）

本題要求計算柱狀圖中能接的雨水量。每個位置的存水量受短邊的影響；可以直接套用單調棧求解，這里寫出另外的兩種解法；

法一:動態規劃法

核心思路是通過構建左右方向的最大值數組，從而得到每個位置的理論盛水高度，最后減去實際柱高總和即得雨水總量。

• 復制原始數組 b = a
• 計算原始數組總和 ss（柱體總面積）

然后從兩個方向遍歷數組，維護兩個單調的數組

讓后計算理論盛水總量

• 每個位置能盛水的理論高度：min(a[i], b[i])
• 累加所有位置的理論高度：s += min(a[i], b[i])

計算實際雨水總量

• 雨水總量 = 理論盛水總量 - 柱體總面積
• return s - ss

最終呈現的時間復雜度為O(3n)

class Solution {
public:int trap(vector<int>& a) {vector<int> b=a;int ss=0;for(auto i:a)ss+=i;for(int i=1;i<a.size();i++)if(a[i]<a[i-1])a[i]=a[i-1];for(int i=b.size()-2;i>=0;i--)if(b[i]<b[i+1])b[i]=b[i+1];int s=0;for(int i=0;i<a.size();i++){s+=min(a[i],b[i]);}return s-ss;}
};

法二：雙指針逐層計算

核心策略是逐層水平累加雨水面積。通過從高度1開始逐步增加水平面，利用雙指針實時掃描有效容器邊界，計算每一層可容納的雨水寬度，最后減去柱體本身面積得到最終雨水總量。

• 雙指針：l=0（左邊界），r=size-1（右邊界）
• 當前高度：h=1（從最低水位開始）
• 盛水輪廓面積：s=0（包括水和柱子的總面積）

逐層累加（當l<=r時循環）

• 找左邊界：跳過所有高度小于當前層高h的柱子

  while (l < r && a[l] < h) l++;
  

  檢查終止條件：當左右指針相遇（l==r）且該處高度小于h時，退出循環

• 找右邊界：跳過所有高度小于當前層高h的柱子

  while (l <= r && a[r] < h) r--;
  

• 計算當前層寬：累加左右邊界間的寬度s += (r - l + 1)

最終雨水總量 = 盛水輪廓面積s - 柱子總面積ss

但是這個方法的時間復雜度為O(n·H)，在最大高度H較小時使用比較好；空間相比上個有所減少；

class Solution {
public:int trap(vector<int>& a) {if (a.empty())return 0;int l = 0, r = a.size() - 1;int h = 1;int s = 0;while (l<=r) {while (l < r && a[l] < h) {l++;}if (l == r) {if (a[l] < h)break;}while (l <= r && a[r] < h) {r--;}if (l > r)break;s += (r - l + 1);h++;}int ss = 0;for (auto i : a) {ss += i;}return s - ss;}
};

類似練習

84. 柱狀圖中最大的矩形 - 力扣（LeetCode）求內部的面積（計算直方圖的最大矩形面積）

---