为了你，我变成狼人模样；

为了你，染上了疯狂~

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）求内部的面积（计算直方图的最大矩形面积）

---