单调栈及其应用

目录

 

一、极简概念

二、几个栗子

1.糟糕的一天（洛谷P2866, USACO 2006 月赛）

2.天气变化

3.长方形（洛谷P1950）

---

 

一、极简概念

单调栈是一种内部元素具有单调性的栈，可以解决“以某个值为最值的最大区间”等问题。

能以O(n)的时间复杂度找到每一个元素右边或左边第一个比它大或小的数。（超级好用艾~  不然可能就得用（毒瘤的）二分+RMQ惹QAQ）

来看几道题就会用了

二、几个栗子

1.糟糕的一天（洛谷P2866, USACO 2006 月赛）

传送门

 转变思路：与其求一头牛能看见几头牛， 不如反过来 ，计算一头牛能被几头牛看见，因为它们的总和是相等的。一只牛能被哪些牛看到呢？左边比它高的牛，再左边更高的牛……只需要维护一个数组，满足这个数组里面存的都是对于第 i 头牛来说，身高一次递增的牛的身高（这个数组是单调递减的）。可以使用栈来进行维护。

假设有6头牛，高度分别为 10，3，7，4，12，2，那么它们分别可以看到 3，0 ，1，0，1，0头牛的头发，其总和为5；栈的实现：最开始栈是空的，原来栈里没有牛，那么答案增加0；身高为3的牛来了，从栈顶开始，把所有身高小于等于3的牛都出栈（这里暂时没有这样的牛），然后自己入栈，自己左边有一头牛，答案增加1；身高为7的牛来了，从栈顶开始，把所有小于等于7的牛都出栈（3就出栈），然后自己入栈，自己左边有一头牛，答案增加1……以此类推。

#include<iostream>
#include<stack>
using namespace std;
long long ans;
stack<int> s;
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		while(!s.empty()&&s.top()<=x)s.pop();
		ans+=s.size();
		s.push(x);
	}
	cout<<ans;
	return 0;
}

2.天气变化

CSUSTOJ | 天气变化

 

#include<iostream>
#include<stack>
using namespace std;
const int M=1e6+6;
int n,a[M];
struct nt{
	int v,id;
}p[M];
stack<nt> s;
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i].v,p[i].id=i;
	a[n]=0;
	s.push(p[n]);
	for(int i=n-1;i;i--){
		while(!s.empty()&&s.top().v<=p[i].v)s.pop();
		if(!s.empty())a[i]=s.top().id-i;
		else a[i]=0;
		s.push(p[i]);
	}
	for(int i=1;i<=n;i++)cout<<a[i]<<' ';
	return 0;
}

3.长方形（洛谷P1950）

P1950 长方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

小明今天突发奇想，想从一张用过的纸中剪出一个长方形。

为了简化问题，小明做出如下规定：

（1）这张纸的长宽分别为 $n,m$。小明讲这张纸看成是由$n\times m$个格子组成，在剪的时候，只能沿着格子的边缘剪。

（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。

（3）剪出来的长方形的大小没有限制。

小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？

输入格式

第一行两个正整数 n,m，表示这张纸的长度和宽度。

接下来有 n 行，每行 m$个字符，每个字符为 `*` 或者 `.`。

字符 `*` 表示以前在这个格子上画过，字符 `.` 表示以前在这个格子上没画过。

 输出格式

仅一个整数，表示方案数。

样例 1

样例输入 1
6 4
....
.***
.*..
.***
...*
.***

 样例输出 1
38

 

 

 书上咋又是数组模拟栈。。看着晕qwq。为啥不直接用stack啊

#include<iostream>
#include<stack>
using namespace std;
const int M=1e3+6;
int n,m,l[M],r[M];
struct nt{
	int h,id;
}p[M];
stack<nt> s;
long long ans;
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	char x;
	for(int i=1;i<=m;i++)p[i].id=i;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>x;
			p[j].h=(x=='*'?0:p[j].h+1);
		}
		while(!s.empty())s.pop();
		for(int j=1;j<=m;j++){
			while(!s.empty()&&s.top().h>p[j].h)s.pop();
			if(!s.empty())l[j]=s.top().id;
			else l[j]=0;
			s.push(p[j]);
		}
		while(!s.empty())s.pop();
		for(int j=m;j;j--){
			while(!s.empty()&&s.top().h>=p[j].h)s.pop();
			if(!s.empty())r[j]=s.top().id;
			else r[j]=m+1;
			s.push(p[j]);
		}
		for(int j=1;j<=m;j++)
			ans+=(j-l[j])*(r[j]-j)*p[j].h;
	}
	cout<<ans;
	return 0;
}

emmmm记得清空栈那里别落了感叹号（非空啊）QAQ晚上捣鼓半天没发现www感谢pbrjjOrzzz