自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:14:23，当前版本为作者最后更新于2019-12-17 13:17:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

update：2019/12/13

$\ \ \ \ \ \ \$觉得写得有点不清楚，稍微改了一下语言以及添加一道例题。

update：2020/2/17

$\ \ \ \ \ \ \$修改了一点错别字，改了一下内容和定义。造成的曲解抱歉了。修改了伪代码使其规范。修改了题解规范。

单调栈

前言

$\ \ \ \ \ \ \$也是晚上突然看到新增加的模板。想着没学多久，想来发篇博客，熟悉一下。

感谢

lucky52529的博客

定义

$\ \ \ \ \ \ \$我们都知道单调队列，也就是在这个队列里面存放的数据应该是有序的。当然，单调栈从这个冷艳的名字就可以看出来，这个栈存放的数据内部对应的顺序也应该是有序的。

$\ \ \ \ \ \ \$我们根据存放下标对应元素的顺序，可以分为两种单调栈：

• 单调递减栈，指的就是栈内存放下标对应元素构成的序列对应的元素单调递减。

• 单调递增栈，指的就是栈内存放下标对应元素构成的序列对应的元素单调递增。

$\ \ \ \ \ \ \$一定注意，我们存放的一般是下标，而不是元素。但是作为比较的标准是下标对应的元素。

模拟

$\ \ \ \ \ \ \$让我们模拟一遍单调栈的运行过程，这里的单调栈是单调递增栈。

$\ \ \ \ \ \ \$我们现在有 $6$ 个数 $5,2,3,4,1,6$。

$\ \ \ \ \ \ \$首先我们要明白，我们存放的是下标。然后，我们直接把元素放在栈顶，会破坏它的单调性。所以我们需要吐出栈顶的元素，使得我们当前的元素再加进去不会破坏它的单调性。

• 我们当前栈内没有元素，将 $5$ 加入。现在栈内元素应该是 $1$。

• 当前元素为 $2$，我们发现加入之后不能单调，于是吐出 $5$，加入 $2$。当前栈内元素为 $2$。

• 接下来是 $3,4$。我们发现加入不会破坏单调性，于是直接加入，栈内元素 $2,3,4$。

• 遇到 $1$，只能吐出栈内所有元素，加入 $1$。

• 最后加入 $6$。整个算法流程完成。

伪代码

$\ \ \ \ \ \ \$我们可以根据这个算法流程，打出伪代码。

stack<int> S;
for i←1 to n
	if S.size=0 || a[S.top]>=a[i]
		then	S.push i
	else
		while S.size && a[S.top]<a[i]
			do	S.pop
			end
		S.push i

$\ \ \ \ \ \ \$我猜是这样，毕竟没学过伪代码。

杂七杂八的问题

$\ \ \ \ \ \ \$对于我自己来说，我学的时候会有一些问题，在这里带着自己的经验解释一下。

1. 单调栈解决的主要问题是什么呢？

$\ \ \ \ \ \ \$就跟单调队列差不多。单调队列主要处理的是一个区间内的最大/小值，而单调栈处理的是寻找以某个值为最小/大值的最大区间。相比较，实际上单调栈用的虽然少一些，但是比单调队列更加灵活多变。

2. 为什么单调栈是正确的呢？

$\ \ \ \ \ \ \$对于这道题来说，我们定义一个元素失效，当且仅当这个元素的 $f_i$ 被保存。我们假设将栈中已有元素。既然栈中元素没有被弹出，那么证明还没有遇到比它大的元素。当我们的元素从栈中弹出的时候，这证明了它发现了第一个比它还要大的数，这道题刚好满足，于是保存 $f_i$ ，继续算法流程。同理，对于之前的主要问题，我们找到了一个比它还要大的数，说明这个区间结束了。

3. 单调栈的时间复杂度是？

$\ \ \ \ \ \ \$想一下，我们的每一个元素最多进栈/出栈一次，所以说时间复杂度 $O(n)$。

$\ \ \ \ \ \ \$下文所说元素可能不是指的下标对应元素而是直接指元素，没有提示请不要混淆。

结束标识符

$\ \ \ \ \ \ \$对于某些特殊题目，栈内元素出不完，会导致答案错误，这时候我们要添加结束标识符强制吐出所有栈内元素。

$\ \ \ \ \ \ \$找个例子：

视野总和

$\ \ \ \ \ \ \$lucky52529的博客，自查第一题。

$\ \ \ \ \ \ \$我们很容易想到构造一个单调递增栈，如果遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值即可。

$\ \ \ \ \ \ \$但是我们发现我们 WA 了，因为遗留在栈里面的人还没有计算贡献。我们于是用结束标识符，这里是极大值，想象一个无限高的人站在最右边，那么我们所有人都能出栈，不会漏掉。

代码

#include<cstdio>
#include<stack>
#include<algorithm>
#define mp make_pair
using namespace std;
stack<long long> S;
long long a[5000005],ans;
int main(){
	long long n;
	scanf("%lld",&n);
	for(long long i=1;i<=n;++i)	scanf("%lld",&a[i]);
	a[n+1]=10086001100860011ll;//结束标识符
	for(long long i=1;i<=n+1;++i)
	{
		if(S.empty() || a[S.top()]>=a[i])	S.push(i);
		else
		{
			while(S.size() && a[S.top()]<a[i])
			{
				long long Top=S.top();
				ans+=(i-Top-1);
				S.pop();
			}
			S.push(i);
		}
	}
	printf("%lld",ans);
	return 0;
}

直方图中最大的矩形

$\ \ \ \ \ \ \$lucky52529的博客，自查第二题。

$\ \ \ \ \ \ \$上面都是用的单调递增栈，这次我们用单调递减栈。我们每次将元素从栈里面弹出的时候，因为我们的答案可能会出现在里面，所以我们弹出元素就计算一遍答案。

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
long long a[100005],n;
stack<long long> S;
void debug()
{
	stack<long long> tmp=S;
	while(tmp.size())	printf("%lld ",tmp.top()),tmp.pop();
	puts("");
}
void Clear()
{
	stack<long long> tmp;
	S=tmp;
}
int main(){
	while(scanf("%lld",&n) && n)
	{
		Clear();
		long long ans=0;
		for(long long i=1;i<=n;++i)	scanf("%lld",&a[i]);
		a[n+1]=-2147483647;
		for(long long i=1;i<=n+1;++i)
		{
			if(S.empty() || a[S.top()]<=a[i])	S.push(i);
			else
			{
				long long Top=0;
				while(S.size() && a[S.top()]>a[i])
				{
//					debug();
					Top=S.top();
					ans=max(ans,(i-Top)*a[Top]);
					S.pop();
				}
				a[Top]=a[i];//why?
				S.push(Top);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

$\ \ \ \ \ \ \$发现我在 a[Top]=a[i]; 这个语句后打了个 //why?。这是为什么呢？

$\ \ \ \ \ \ \$我们弹出元素计算答案，相信大家都能够理解。但是为什么要更改我们的 $a$ 数组呢？

$\ \ \ \ \ \ \$举个例子：$2,3,1$。

$\ \ \ \ \ \ \$思考一下，我们要维持它单调，假设加入 $3$ 这个元素的时候栈只有它一个元素。我们的 $top$ 会从 $1$ 变成 $3$。但是 $1,2$ 两个元素对应的值都比它大。但是我们为了保持栈中的递增属性，并且可以让向左拓展，我们索性修改了 $i$ 的下标，将他修改为最左边的 $top$ 下标，所以当我们下次需要以他为基准获取矩形面积。

题解

$\ \ \ \ \ \ \$对于这道题，我们构造一个单调递增栈，我们可以想象，我们每次出栈，都是因为找到了一个比当前栈顶元素大的元素，可以证明它一定是最早出现的，于是用数组记录答案，每次出栈保存答案。注意卡常。

#include<cstdio>
int a[3000005],f[3000005],S[3000005],n;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0' || c>'9')
	{
		if(c=='-')	f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}
void write(int x)
{
	if(x<0)	putchar('-'),x=-x;
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)	a[i]=read();
	int top=0;//用数组模拟栈，不然会T
	for(int i=1;i<=n;++i)
	{
		while(top && !(a[S[top]]>=a[i]))	f[S[top--]]=i;//我们发现直接加入会破坏单调性，于是弹出栈顶元素，顺便计算当前元素的答案
		S[++top]=i;
	}
	for(int i=1;i<=n;++i)	write(f[i]),putchar(' ');
	return 0;
}

例题

$\ \ \ \ \ \ \$AT1225，CDQ分治套单调栈，较难。

$\ \ \ \ \ \ \$lucky52529的博客，自查第三题。