题解 P5788 【【模板】单调栈】
FjswYuzu
·
·
题解
update：2019/12/13
update：2020/2/17
$\ \ \ \ \ \ \ $修改了一点错别字，改了一下内容和定义。造成的曲解抱歉了。修改了伪代码使其规范。修改了题解规范。
# 单调栈
## 前言
$\ \ \ \ \ \ \ $也是晚上突然看到新增加的模板。想着没学多久，想来发篇博客，熟悉一下。
## 感谢
[lucky52529的博客](https://blog.csdn.net/lucky52529/article/details/89155694)
## 定义
$\ \ \ \ \ \ \ $我们都知道单调队列，也就是在这个队列里面存放的数据应该是有序的。当然，单调栈从这个冷艳的名字就可以看出来，这个栈存放的数据内部对应的顺序也应该是有序的。
$\ \ \ \ \ \ \ $我们根据存放下标对应元素的顺序，可以分为两种单调栈：
- 单调递减栈，指的就是栈内存放下标对应元素构成的序列对应的元素单调递减。
- 单调递增栈，指的就是栈内存放下标对应元素构成的序列对应的元素单调递增。
$\ \ \ \ \ \ \ $**一定注意，我们存放的一般是下标，而不是元素。但是作为比较的标准是下标对应的元素**。
## 模拟
$\ \ \ \ \ \ \ $让我们模拟一遍单调栈的运行过程，这里的单调栈是单调递增栈。
$\ \ \ \ \ \ \ $我们现在有 $6$ 个数 $5,2,3,4,1,6$。
$\ \ \ \ \ \ \ $首先我们要明白，我们存放的是下标。然后，我们直接把元素放在栈顶，会破坏它的单调性。所以我们需要吐出栈顶的元素，使得我们当前的元素再加进去不会破坏它的单调性。
- 我们当前栈内没有元素，将 $5$ 加入。现在栈内元素应该是 $1$。
- 当前元素为 $2$，我们发现加入之后不能单调，于是吐出 $5$，加入 $2$。当前栈内元素为 $2$。
- 接下来是 $3,4$。我们发现加入不会破坏单调性，于是直接加入，栈内元素 $2,3,4$。
- 遇到 $1$，只能吐出栈内所有元素，加入 $1$。
- 最后加入 $6$。整个算法流程完成。
## 伪代码
$\ \ \ \ \ \ \ $我们可以根据这个算法流程，打出伪代码。
```cpp
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的博客](https://blog.csdn.net/lucky52529/article/details/89155694)，自查第一题。
$\ \ \ \ \ \ \ $我们很容易想到构造一个单调递增栈，如果遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值即可。
$\ \ \ \ \ \ \ $但是我们发现我们 WA 了，因为遗留在栈里面的人还没有计算贡献。我们于是用结束标识符，这里是极大值，想象一个无限高的人站在最右边，那么我们所有人都能出栈，不会漏掉。
#### 代码
```cpp
#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的博客](https://blog.csdn.net/lucky52529/article/details/89155694)，自查第二题。
$\ \ \ \ \ \ \ $上面都是用的单调递增栈，这次我们用单调递减栈。我们每次将元素从栈里面弹出的时候，因为我们的答案可能会出现在里面，所以我们弹出元素就计算一遍答案。
#### 代码
```cpp
#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$ 下标，所以当我们下次需要以他为基准获取矩形面积。
### 题解
$\ \ \ \ \ \ \ $对于这道题，我们构造一个单调递增栈，我们可以想象，我们每次出栈，都是因为找到了一个比当前栈顶元素大的元素，可以证明它一定是最早出现的，于是用数组记录答案，每次出栈保存答案。注意卡常。
```cpp
#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](https://www.luogu.com.cn/problem/AT1225)，CDQ分治套单调栈，较难。
$\ \ \ \ \ \ \ $[lucky52529的博客](https://blog.csdn.net/lucky52529/article/details/89155694)，自查第三题。