就是有口无肛门的动物, 先进的后出
一般使用 \(stack\) 实现代码
括号匹配
判断是否合法
遇到左括号就入栈, 右括号就出栈, 保证栈不为空
合法括号序列计数
卡特兰数
单调栈
在栈内维护一个单调的序列, 经典例题是找到右边第一个比他大或者小的值的位置, 一种可行的代码:
for (int i = n; i >= 1; i--) {
while ((!s.empty()) && a[s.top()] <= a[i]) s.pop();
if (s.empty()) ans[i] = 0;
else ans[i] = s.top();
s.push(i);
}
rmq问题
单调栈可以用来求解 \(rmq\) 问题
我们发现区间最大值在单调栈过程中是单调栈最左边的值, 利用这个性质我们可以在单调栈上二分, 或者利用一些奇怪的方法找到这个值
所以具体做法就是, 首先把询问都离线下来, 然后从左到右做单调栈, 遍历到一个点的时候, 处理所有区间的右端点是这个点的询问, 利用二分查找答案
例题
最大子矩形问题原题, 枚举那个点是必定是被完全包含的, 然后贪心的利用单调栈扩展左右边界
二维的最大子矩形, 先按照一维做消去一维, 然后就是问题一了
与问题二很像, 于是考虑怎么转换成问题二,
0101
1010
怎么变成
1111
1111
很简单, 让下标\((i,j)\) 满足 \((i + j) \mod 2 = 0\) 的点颜色反转即可
答案一可以使用 \(DP\) 求解
看着就比较像单调栈, 考虑一种特殊情况: 具有相同高度的, 可以开 \(pair\) 记录相同高度的有多少人
贡献有两种, 一种两边是最大值和次大值
这个是单调栈模拟的时候就会产生 并且可以发现个数是 \(O(n)\) 级别的, 然后就可以离线二维数点
单调栈的第二种应用就是类似于kruscal 重构树的操作, 就是给你一个限制的高度, 问你能扩展到哪个区间, 用单调栈可以非常简单的实现这个操作
第二种贡献就是模拟题意的, 枚举哪个值是最大的, 然后向两边扩展, 然后观察合法的区间就是一条横线或者竖线, 做两次扫描线就可以了
表达式求值
这个东西是模拟, 我没有系统的学习过, 比较菜, 这里写一下
这个其实也是单调栈的应用
我们会发现任何一个运算两边总会是数字, 于是我们可以这样定义一次运算, 就是把两边的数字拿出来, 然后运算出来再插回去, 我们发现这永远满足任何一个运算符两边总会是数字
然后每一个运算都定义一个优先级, 优先级越高就先运算, 然后乘法是2, 加法是1, 括号里的相当于都加3 我们发现这样搞出来是对的
然后我们有这些东西怎么去模拟呢, 通过单调栈! 这样是不是就清晰多了
我们也可以根据这个建立出来表达式树, 做更多的操作
自左向右处理表达式具体的操作：
-
若遇到数字则压入数字栈。
-
若遇到左括号则压入符号栈。
-
若遇到加减号，则一直弹栈直到符号栈空/栈顶为左括号，将这个运算符压入符号栈。
-
若遇到乘除号，则一直弹栈直到符号栈空/栈顶为左括号或加减号，将这个运算符压入符号栈。
-
若遇到右括号，则一直弹栈直到弹出一个左括号为止。
例题
模拟, 把 \(a\) 随机一个值在模意义下一样我们就认为是一样的
标签：,运算,压入,然后,运算符,括号,单调 From： https://www.cnblogs.com/aqz180321/p/18415963