单调栈详解

发布于:2024-10-10 ⋅ 阅读:(98) ⋅ 点赞:(0)

单调栈的定义

单调递增栈

  • 栈中元素从栈底到栈顶是递增的。

单调递减栈

  • 栈中元素从栈底到栈顶是递减的。

单调栈的核心内容

我们从左到右遍历元素,构造单调栈(从栈顶到栈底递增或减):在 i 从左往右遍历的过程中,我们可以用一个单调栈来保存 i 左边的所有元素(不包括 i 指向的元素),i 遍历一个元素单调栈就放入一个元素,每一个元素都必须入栈一次下标越大的元素越接近栈顶,下标越小的元素越接近栈底。

在每个新的元素入栈前从栈顶依次去除所有不合法的元素,因为这些元素会破坏单调性,直到栈顶小于或大于该入栈元素,此时元素可以入栈。

简单来说,就是在入栈时删掉不合法元素,保证栈的单调性。

单调栈的应用

寻找左边第一个比它小的数

例题

给定一个长度为 N 的数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。

Sol

朴素算法的时间复杂度为\Theta(N^2),所以考虑优化。

在元素入栈前从栈顶依次去除所有不合法元素,因为这些元素会破坏单调性,直到栈顶小于该入栈元素,此时元素可以入栈,栈的单调性没被破坏,并且此时的栈顶就是要寻找的答案——左边第一个比它小的数。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=1;i<=n;i++){
		while(!stk.empty() && stk.top()>=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		else
			ans[i]=-1;
		stk.push(arr[i]);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找左边第一个比它大的数

和上面的思路相同。改变符号即可。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=1;i<=n;i++){
		while(!stk.empty() && stk.top()<=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		else
			ans[i]=-1;
		stk.push(arr[i]);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找左边第一个比它小的数的下标

Sol

很简单,我们让栈维护的是下标即可。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=1;i<=n;i++){
		while(!stk.empty() && arr[stk.top()]>=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		stk.push(i);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找左边第一个比它大的数的下标

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=1;i<=n;i++){
		while(!stk.empty() && arr[stk.top()]<=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		stk.push(i);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找右边第一个小于它的数

Sol

将数组倒序遍历即可。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=n;i>0;i--){
		while(!stk.empty() && stk.top()>=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		else
			ans[i]=-1;
		stk.push(arr[i]);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找右边第一个大于它的数

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=n;i>0;i--){
		while(!stk.empty() && stk.top()<=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		else
			ans[i]=-1;
		stk.push(arr[i]);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找右边第一个小于它的数的下标

例题:P5788

Sol

和之前的思路相同。

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=n;i>0;i--){
		while(!stk.empty() && arr[stk.top()]>=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		stk.push(i);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

寻找右边第一个大于它的数的下标

Code

#include <bits/stdc++.h>
using namespace std;
int arr[maxn],ans[maxn];
stack<int> stk;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>arr[i];
	for(int i=n;i>0;i--){
		while(!stk.empty() && arr[stk.top()]<=arr[i])
			stk.pop();//把栈内不合法的元素出栈
		if(!stk.empty())
			ans[i]=stk.top();//栈顶就是答案
		stk.push(i);
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<' ';
	return 0;
}

以上就是本期博客的全部内容了,我这就去更新 ABC372 的题解


网站公告

今日签到

点亮在社区的每一天
去签到