栈是 OI 中常用的一种线性数据结构。
栈的修改是按照后进先出的原则进行的,因此栈通常被称为是后进先出(last in first out)表,简称 LIFO 表。
下文均使用名为 st
,栈底为 st[1]
,栈顶为 st[top]
的数组模拟栈。
这样做的好处是,操作方便:
操作 | 代码 |
---|---|
查询栈的大小 | top |
查询栈是否为空 | top |
查询栈顶元素 | st[top] |
插入元素 | st[++top] = x; |
弹出栈顶元素 | top--; |
顾名思义,单调栈即满足单调性的栈结构。与单调队列相比,其只在一端进行进出。
严格不等式:只含有记号 或 的不等式称为严格不等式。
非严格不等式:含有记号 或 的不等式称非严格不等式。
所以「严格大于」就是 ,「严格小于」就是 。
严格单调递增(减),指的是除第一个元素外,每个元素都严格大于(小于)前一个元素。
考虑这样一个问题:给定一个数列,对于每个数,求出这个数之前第一个严格大于它的数。
假设该数列为:,依次将元素插入栈。
如图 1-1,此时已插入前 个元素,下一个待插入元素为 。
图 1-1(图自 OI-Wiki)
为了找到 之前第一个比它大的元素,要维护单调性,将比 小的元素弹出,于是弹出 和
如图 1-2,此时栈中 的前一个元素为 ,所以 之前第一个大于它的元素是 。
图 1-2(图自 OI-Wiki)
假设下一个插入的元素为 。
如果 ,那么那么 肯定不是(元素 的)答案,那么比 还小的 就更不可能是答案。
如果 ,那么 就是答案,不用再考虑 。
所以, 不会再对后面的答案产生贡献(影响),可以弹出。
借助单调性处理问题的思想在于及时排除不可能的选项,保持策略的高度有效性和秩序性,从而为我们作出决策提供更多的条件和可能的方法。
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int n = 6;
int a[6] = {81, 45, 11, 0, 14, 26}, ans[6] = { };
int st[6] = { }, top = 0;
for(int i = 0; i < n; i++){
while(top && st[top] <= a[i]){ // 注意要用 top 判栈是否为空,不为空才能判断
printf("pop %d.\n", st[top]);
top--;
}
if(top){
ans[i] = st[top];
}else{
ans[i] = -1; // 前面没有比这个数大的,就输出 -1
}
printf("push %d.\n", a[i]);
st[++top] = a[i];
printf("stack: ");
for(int j = 1; j <= top; j++){
printf("%d ", st[j]);
}
puts("\n");
}
printf("ans: ");
for(int i = 0; i < n; i++){
printf("%d ", ans[i]);
}
return 0;
}
运行结果:
push 81.
stack: 81
push 45.
stack: 81 45
push 11.
stack: 81 45 11
push 0.
stack: 81 45 11 0
pop 0.
pop 11.
push 14.
stack: 81 45 14
pop 14.
push 26.
stack: 81 45 26
ans: -1 81 45 11 45 45
空间复杂度显然为 。
观察代码核心部分:
// ……
for(int i = 0; i < n; i++){
while(top && st[top] <= a[i]){
printf("pop %d.\n", st[top]);
top--;
}
// ……
}
// ……
注意里层的 while
循环,是用于弹出栈顶小于待插入元素的元素。
每个元素只入栈一次,也只会出栈一次,所以里层 while
循环总共只会执行 次,整个单调栈代码的时间复杂度为 。
给定一个长度为 的数列,对于每个数,求出这个数之后第一个严格大于它的元素的下标。
发现正着做单调栈无法处理,考虑反着做。
此时就需要维护一个严格单调递减的栈,即插入元素前把栈顶小于它的元素全部弹出。
插入前如果栈为空,则答案为 ,否则为栈顶元素。
这题的一个要注意的点在于,要求的是元素的下标,所以栈要存储下标,而非数据。
题目使用的下标为 ,方便起见程序的下标也用 。
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 3e6 + 10;
int n, a[N], ans[N];
int st[N], top;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
for(int i = n; i > 0; i--){
while(top && a[st[top]] <= a[i]){
top--;
}
if(top){
ans[i] = st[top];
}else{
ans[i] = 0;
}
st[++top] = i;
}
for(int i = 1; i <= n; i++){
printf("%d ", ans[i]);
}
return 0;
}
Luogu P2866 [USACO06NOV]Bad Hair Day S
有 头奶牛排成一队,每只奶牛有一个身高 ,求每只奶牛可以看到前方多少只奶牛的头发的和。
奶牛 A 看到了奶牛 B 的头发,就相当于奶牛 B 的头发被奶牛 A 看到了。
求每只奶牛可以看见后面多少个奶牛的头发比较困难,但可以求每只奶牛的头发可以被前面多少只奶牛看见,这两个求法最终的和是一样的。
于是问题就被转化为「每只奶牛的头发可以被前面多少只奶牛看见」。
使用单调栈,维护一个严格单调递减的栈。
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 8e4 + 10;
int n, x;
int st[N], top;
long long ans;
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &x);
while(top && st[top] <= x){
top--;
}
ans += top;
st[++top] = x;
}
printf("%lld\n", ans);
return 0;
}
其实是 RMQ 模板题。
给定 个数和 组询问,每组询问有一个区间 ,求该区间最大值。
RMQ 是英文 Range Maximum(Minimum) Query 的缩写,意思是查询区间最大(最小)值。
常见算法:
算法 | 是否在线 | 预处理时间复杂度 | 单次询问时间复杂度 | 总时间复杂度 | 空间复杂度 |
---|---|---|---|---|---|
ST 表 | 在线 | ||||
线段树 | 在线 | ||||
…… | …… | …… | …… | …… | …… |
单调栈 | 离线 |
其中 为数组大小, 为询问次数。
详细内容可以前往 RMQ - OI Wiki 查看。
如果某种算法可以即时回答每一个询问,则称该算法为在线的,否则称为离线的。
读入所有询问,然后按询问的右端点从小到大排序。
依次处理元素,维护严格单调递减栈。
如果处理到某个询问的右端点,则二分单调栈,找出栈底开始第一个下标大于此次询问的 的元素,记录答案。
详见代码注释。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;
struct qt{
int id, l, r;
}q[M]; // 结构体存储询问
int n, a[N], m;
int st[N], top;
int ans[M];
bool cmp(qt x, qt y){
return x.r < y.r;
} // 按右端点从小到大排序
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
for(int i = 0; i < m; i++){
q[i].id = i;
scanf("%d%d", &q[i].l, &q[i].r);
}
sort(q, q+m, cmp);
int nw = 0; // 当前处理的询问
for(int i = 1; i <= n && nw < m; i++){ // 依次处理每一个元素,插入栈中,维护严格单调递减栈
while(top && a[st[top]] <= a[i]){
top--;
}
st[++top] = i;
while(i == q[nw].r){ // 如果当前处理到某一个询问的右端点(因为右端点可能重复,所以用 while 而非 if)
int l = 1, r = top; // 二分栈中第一个下标大于此次询问的 l 的元素
while(l < r){
int mid = (l + r) / 2;
if(st[mid] >= q[nw].l){
r = mid;
}else{
l = mid + 1;
}
}
ans[q[nw].id] = a[st[l]]; // 记录答案
nw++; // 处理下一个问题
}
}
for(int i = 0; i < m; i++){
printf("%d\n", ans[i]);
}
return 0;
}
维护一个栈,使得其存储的数据具有单调性,这样的栈叫做单调栈。
单调栈用于求解「序列中元素左/右第一个比它大/小的元素」。
因为每个元素最多各自进出栈一次,所以时间复杂度为 。
单调栈经常会搭配别的算法,常见的例如二分。
POJ 2559 Largest Rectangle in a Histogram
给定 个柱子的高,求出组成的多边形中最大的矩形的面积。
观察发现,框出的最大矩形一定是以某个柱子为高的。
枚举每根柱子,找出左边第一个比它短的柱子,和右边第一个比它短的柱子,就可以算出以这个柱子为高的最大矩形的面积,最后所有答案取最大值即可。
「找出左边第一个比它短的柱子,和右边第一个比它短的柱子」用单调栈处理即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
int n;
int h[N], l[N], r[N];
int st[N], top;
long long ans;
int main(){
while(scanf("%d", &n), n != 0){
ans = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &h[i]);
}
// 处理左边第一个比它短的柱子
top = 0;
for(int i = 1; i <= n; i++){
while(top && h[st[top]] >= h[i]){
top--;
}
// if(top){
// l[i] = st[top];
// }else{
// l[i] = 0;
// }
// 如果 top == 0,st[top] == st[0] == 0,所以也可以写成下面这个样子:
l[i] = st[top];
st[++top] = i;
}
// 处理有边第一个比它短的柱子
top = 0;
for(int i = n; i > 0; i--){
while(top && h[st[top]] >= h[i]){
top--;
}
if(top){
r[i] = st[top];
}else{
r[i] = n+1;
}
st[++top] = i;
}
for(int i = 1; i <= n; i++){
ans = max(ans, (long long)(r[i]-l[i]-1)*h[i]);
} // 分别算出以每个柱子为高的矩形的最大面积
printf("%lld\n", ans);
}
return 0;
}