单调栈详解+例题

猿柒

19天前发布

昨天打 AT 碰到了一道单调栈的题，于是来复习一下

单调栈

栈内元素单调性
有单调递增栈 和 单调递减栈

实现：

举个例子：

假设入栈序列为

1 4 2 8 9 3

要模拟一个单调递增栈：

\(i=1\) 时，栈为空，\(1\) 入栈后仍然保持单调性，将 \(1\) 入栈；
\(i=2\) 时，栈顶元素为 \(1\)，\(4\) 入栈后仍然保持单调性，将 \(4\) 入栈；
\(i=3\) 时，栈顶元素为 \(4\)，\(2\) 入栈后不满足单调性，\(4\) 出栈。
此时 \(2\) 入栈后能保持单调性，\(2\) 入栈；
\(i=4\) 时，栈顶元素为 \(2\)，\(8\) 入栈后仍然保持单调性，将 \(8\) 入栈；
\(i=5\) 时，栈顶元素为 \(8\)，\(9\) 入栈后仍然保持单调性，将 \(9\) 入栈；
\(i=6\) 时，栈顶元素为 \(9\)，\(3\) 入栈后不满足单调性，\(9\)出栈。
这时栈顶元素为 \(8\)，\(3\) 入栈后不满足单调性，\(8\)出栈。
此时 \(3\) 入栈后能保持单调性，\(3\) 入栈；

代码：

stack<int>st;//栈里面存下标 

for(int i=1;i<=n;i++)
{
	while(!st.empty()&&a[st.top()]>a[i])//a[i]入栈后不是单调递增的
		st.pop();//出栈
	……//更新答案 
	st.push(i); 
}

那它有什么用呢？

洛谷模板题

题目大意：

给你一个数列 \(a\)，求数列中第 \(i\) 个元素后面第一个大于它的元素的下标

思路：

思路一：建立一个单调递减的栈
按照顺序入栈
如果一个数入栈就不满足单调递减了，证明这个数是目前栈顶的元素后面第一个大于它的元素的下标
记录答案
思路二：建立一个单调递减的栈
倒序入栈
如果一个数入栈就不满足单调递减了，栈顶出栈
最后栈顶就是此时入栈元素后面第一个大于它的元素的下标
记录答案

完整代码：

思路一：

#include<bits/stdc++.h>

using namespace std;

int n;
int a[3000100];
int f[3000100];
stack<int>st;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		while(!st.empty()&&a[st.top()]<a[i]){
			f[st.top()]=i;
			st.pop();
		}
		st.push(i);
	}
	for(int i=1;i<=n;i++)
	{
		cout<<f[i]<<(i!=n?" ":"\n");
	}
	return 0;
}

思路二：

#include<bits/stdc++.h>

using namespace std;

int n;
int a[3000100];
stack<int>st;
int f[3000100];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	 } 
	for(int i=n;i>=1;i--)
	{
		while(!st.empty()&&a[st.top()]<=a[i]) st.pop();
		if(!st.empty())f[i]=st.top();//这里要特别判断一下是否为空
		else f[i]=0;
		st.push(i);
	}
	for(int i=1;i<=n;i++)
	{
		cout<<f[i]<<(i!=n?" ":"\n");
	}
	return 0;
}