单调栈
liangjinglong · · 个人记录
单调栈
从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈
-
单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
-
单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大
- 10入栈时，栈为空，直接入栈，栈内元素为10。
- 3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。
- 7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。
- 4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。
- 12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。
例题1
luogu P2866 [USACO06NOV]Bad Hair Day S
用数据说话
输入#1
6
10 3 7 4 12 2看数据范围，要是暴力枚举是100%会T掉的
个子10能看见3的，7的，4的发型 tot=3;
7能看见4的 tot+=1；tot=4；
12能看见2的 tot+=1，tot=5；
所以答案是5
不难发现，这个题是用单调栈
根据单调栈的原理
1: 10入栈,tot=0;
2: 3入栈 tot++；tot=1
3: 7入栈，3弹出，tot+=2；tot=3;
4: 4入栈，tot++;tot=4；
5.12进栈，弹出栈内所有元素
6.2进栈tot++，tot=5；
答案就是5了
#include<bits/stdc++.h>
using namespace std;
long long stk[3000000+50];
long long a[3000000+50];
long long ans;
long long n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
long long top=0;
for(int i=1;i<=n;i++){
while(top&&(stk[top]<=a[i]))top--;
ans+=top;
stk[++top]=a[i];
}
cout<<ans;
}例题2
luogu P3467 [POI2008]PLA-Postering
题目简述：N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.
我们发现：答案与宽度是没有关系的，于是我们只需要按高度维护一个单调递增的栈。
如果发现当前高度已经在栈中，就不需要另外一张海报了。
5
1 2
1 3
2 2
2 5
1 4我们看样例啊
简化后是这个样子的
5
2 3 2 5 4去掉宽度后的图像
而我们要求的
是个这个
那应该还用单调栈去实现
参考题解的说法
1.考虑如果整个建筑物链是等高的，一张高为链高，宽为整个建筑物宽的海报即可完全覆盖；
2.若有两个不等高的元素组成建筑物链，那么一定需要两张；
3.因为题目要求海报不可超出建筑物链，那么我们即可用单调栈维护：初始海报数为建筑物数，入栈建筑物链的高度序列，当栈顶大于即将入栈元素时弹栈，若最后弹栈元素与即将入栈元素等高，需要的海报数-1；
4.易证明本方法是正确的：当有两个处于一个峰两侧的等高块时，他们可以用一张海报覆盖，所需海报数显然可减少一个；
#include<bits/stdc++.h>
using namespace std;
long long top=0,n,num=0,i,j,k,stk[250100];
int main(){
scanf("%lld",&n);
for(i=1;i<=n;++i){
scanf("%lld%lld",&j,&k);
while(top>0&&k<=stk[top]){
if(k==stk[top])num++;
--top;
}
stk[++top]=k;
}
printf("%lld\n",n-num);
return 0;
}
为什么是n-num呢？
根据代码的做法
初始海报数就是建筑物数量
num就是不需要的海报数
所以用n-num为答案