单调栈问题

53 阅读 0 评论 35 点赞

我是靠谱客的博主还单身鸡翅，最近开发中收集的这篇文章主要介绍单调栈问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

单调栈能够求得 该数左边离他最近的大于/小于的数（其他问题也可以转换为此问题）

例如求 a[i]左边第一个小于a[i]的数

对于a[i]每次入栈如果有大于等于a[i]的数，直接出栈

证明：如果求左侧第一个小于a[i]的数

如果a[i]入栈后左侧有大于a[i]的数，则那个数不仅是大值而且还出现的比较早，所以他永远不会被用到，所以直接出栈

单调栈板子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=3e6+10;
int a[N],q[N],ans[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int tt=0;
for(int i=n-1;i>=0;i--)
{
	while(tt&&a[q[tt]]<=a[i])tt--;
	if(tt)ans[i]=q[tt]+1;
	else ans[i]=0;
	q[++tt]=i;
}
for(int i=0;i<n;i++)cout<<ans[i]<<" ";
return 0;
}

奶牛排队

奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 A 是最矮的，最右边的 B 是最高的，且 BB 高于 AA 奶牛。中间如果存在奶牛，则身高不能和 A,BA,B 奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 0,2，但不会是 1）。

输入格式

第一行一个正整数 NN，表示奶牛的头数。

接下来 NN 行，每行一个正整数，从上到下表示从左到右奶牛的身高 h_ihi。

输出格式

一行一个整数，表示最多奶牛数。

输入输出样例

输入 #1复制
5
1
2
3
4
1
输出 #1复制
4
说明/提示

样例解释

取第 11 头到第 44 头奶牛，满足条件且为最多。

题目大意：找个一个区间[A,B] A最小，B最大的区间

因为 A是区间内最矮的，所以 [A.B]中，都比 A 高。所以只要 AA 右侧第一个 ≤A 的奶牛位于 B 的右侧，则 A 合法

同理，因为B是区间内最高的，所以 [A.B] 中，都比 B 矮。所以只要 B 左侧第一个 ≥B≥B 的奶牛位于 A 的左侧，则 B 合法

用两个单调栈，对于每个a[i] 求它右侧第一个小于a[i]的下标，求他左侧第一个大于a[i]的下标

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int a[N],l[N],r[N],q[N];
int main()
{

//区间[A,B]找到A右侧第一个小于A的下标
//         找到B左侧第一个大于B的下标
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&a[i]);
	}
	int tt=0;
	for(int i=1; i<=n; i++)
	{
		while(tt&&a[q[tt]]<=a[i])tt--;//因为要求的是最大值，所以小于等于都不要
		if(tt)l[i]=q[tt];
		else l[i]=0;
		q[++tt]=i;
//	cout<<l[i]<<" ";
	}

	tt=0;
	for(int i=n; i>=1; i--)
	{
		while(tt&&a[q[tt]]>=a[i])tt--;//因为要求的是最小值，所以大于等于都不要
		if(tt)r[i]=q[tt];
		else r[i]=n+1;//右侧如果没有比他大的则设为N+1 
		q[++tt]=i;
//	cout<<r[i]<<" ";
	}
	int ans=0;
	for(int i=n;i>=1; i--)
	{
		for(int j=l[i]+1; j<i; j++)
		{
			if(r[j]>i)
				ans=max(ans,i-j+1);
		}
		if(i<ans)break;//剪枝 
	}
	printf("%d",ans);


	return 0;
}

良好的感觉

对于一个区间求temp=sum[l~r]*a[i]的最值

暴力解法，对于a[i]求左侧第一个小于该值的下标，求右侧第一个小于该值的下标，得到区间L ~R然后前缀和*a[i]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N],l[N],r[N],q[N],sum[N];
int main()
{

//????[A,B]?òμ?Aóò2àμúò???D?óúμèóúAμ???±ê
//         ?òμ?B×ó2àμúò???′óóúμèóúBμ???±ê
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	int tt=0;
	for(int i=1; i<=n; i++)
	{
		while(tt&&a[q[tt]]>=a[i])tt--;
		if(tt)l[i]=q[tt];
		else l[i]=0;
		q[++tt]=i;
//	cout<<l[i]<<" ";
	}

	tt=0;
	for(int i=n; i>=1; i--)
	{
		while(tt&&a[q[tt]]>=a[i])tt--;
		if(tt)r[i]=q[tt];
		else r[i]=n+1;
		q[++tt]=i;
//	cout<<r[i]<<" ";
	}
	LL ans=0;
	for(int i=1;i<=n; i++)
	{
		LL temp=(sum[ r[i]-1 ]-sum[ l[i] ])*a[i];
		ans=max(ans,temp);
	
	}
	printf("%lld",ans);


	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N],l[N],r[N],q[N],sum[N];
int main()
{

//区间[A,B]找到A右侧第一个小于等于A的下标
//         找到B左侧第一个大于等于B的下标
	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	n++;
	a[n]=0;
	sum[n]=sum[n-1]+a[n];
	int tt=0;
	for(int i=1; i<=n; i++)
	{
		
		
		while(a[q[tt]]>a[i])
		{
			l[q[tt]]+=sum[i-1]-sum[q[tt]];
			tt--;
		}
		l[i]=sum[i]-sum[ q[tt] ];

		q[++tt]=i;
	}



	LL ans=0;
	for(int i=1; i<=n; i++)
	{
	
		LL temp=(l[i]*a[i ] );
	
		ans=max(ans,temp);

	}
	printf("%lld",ans);


	return 0;
}