算法总结——单调栈

纵有疾风起，人生不言弃。本文篇幅较长，如有错误请不吝赐教，感谢支持。

一、单调栈的定义

单调栈不是一种新的数据结构，它在结构上仍然是一个普通栈，只是在使用方法上有所区别。单调栈内的元素是单调递增或递减的，因此有单调递增栈和单调递减栈。

• 单调递增栈： 栈中元素从栈底到栈顶是递增的。
• 单调递减栈： 栈中元素从栈底到栈顶是递减的。

我们在使用单调栈的时候，要时刻保证栈的单调性，例如，单调递增栈：栈中元素从栈底到栈顶是递增的。当一个元素入栈时，与栈顶比较，若比栈顶大，则入栈；若比栈项小,则弹出栈顶，直到这个数能入栈为止。注意：每个元素都一定入栈。
单调栈的核心思想就是：

及时去掉无用数据，保证栈中数据有序

二、单调栈的应用：

单调栈的应用：用来在一个数组中寻找某一个元素左边（或右边）第一个大于（或小于或大于等于或小于等于）它的元素（或元素的下标）。

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

题目练习： AcWing 830. 单调栈
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 ?1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 ?1。
数据范围
1≤N≤10$5$
1≤数列中元素≤$10^9$
输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

思路：传统的暴力做法是双重循环，两个指针i和j，i用来遍历序列，j用来扫描i左边的所有数。时间复杂度是O($n^2$)

#include<iostream>

using namespace std;

const int Max = 1e5 + 10;

int n,arr[Max];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    for (int i = 0; i < n; i++) {
        bool flag = false;//标志 
        for (int j = i - 1; j>=0; j--) {
            if (arr[j] < arr[i]) {
                flag = true;
                cout << arr[j] << ' ';
                break;
            }
        }
        if (!flag) cout << -1 << ' ';
		//如果flag为false，说明左边没有比该元素小的 
    } 
    return 0;
}

我们要是使用单调栈可以将时间复杂度优化到O(n)。
单调栈的思想（ 及时去掉无用数据，保证栈中数据有序）：
在指针 i 从左往右遍历的过程中，我们可以用一个栈来保存 i左边的所有元素（不包括i指向的元素），下标越大的元素越接近栈顶，下标越小的元素越接近栈底，然后从栈顶开始找符合条件的(小于该元素)，把栈内不符合条件的无用数据全部出栈(大于等于该元素)，无用数据之后再也用不到了,最后的栈顶就是答案。
我们来举一个例子：
2 4 5 3 1假如此时3入栈；3左边的4、5都没有存在的必要了（因为3比4和5更小，并且更靠近下一个即将入栈的元素），4、5出栈，然后2比3小，停下符合条件，最后的栈顶2就是答案。
代码：

#include<iostream>
#include<stack>
using namespace std;
const int Max=1e5+10;
int n,arr[Max],ans[Max];
stack<int> stk;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];//arr完整数组
	for(int i=0;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=0;i<n;i++) cout<<ans[i]<<' ';
	return 0;
}

注：arr数组和ans数组可以不创建，但为了方便统一单调栈的格式，所以创建。

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

与上面的差不多，注意到之前我们寻找的是元素所以让栈去保存元素，现在我们寻找下标，所以让栈去保存元素的下标就可以了

#include<iostream>
#include<stack>
using namespace std;
const int Max=1e5+10;
int n,arr[Max],ans[Max];
stack<int> stk;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];//arr完整数组
	for(int i=0;i<n;i++)
	{
		while(!stk.empty()&&arr[stk.top()]>=arr[i]) stk.pop();//把栈内不符合条件的无用数据全部出栈(大于等于该元素)，
		if(!stk.empty()) ans[i]=stk.top();//最后的栈顶就是答案。
		else ans[i]=-1;
		stk.push(i);
	}
	for(int i=0;i<n;i++) cout<<ans[i]<<' ';
	return 0;
}

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

寻找右边，我们可以换一种思想，将数组翻转，转换为寻找左边第一个小于自己的数 ，实际上不可能翻转，而是倒序遍历，因此变成了寻找一个数左边第一个小于它的数，于是归结为情形一。

#include<iostream>
#include<stack>
using namespace std;
const int Max=1e5+10;
int n,arr[Max],ans[Max];
stack<int> stk;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];//arr完整数组
	for(int i=n-1;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=0;i<n;i++) cout<<ans[i]<<' ';
	return 0;
}

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

P5788 【模板】单调栈
题目描述

给出项数为 $n$ 的整数数列 $a_{1\dots n}$。

定义函数 $f(i)$ 代表数列中第 $i$ 个元素之后第一个大于 $a_i$ 的元素的下标，即 f ( i ) = min ? i < j ≤ n , a j > a i { j } f(i)=\min_{i<j\leq n, a_j > a_i} \{j\} f(i)=mini<j≤n,aj?>ai??{j}。若不存在，则 $f(i)=0$。

试求出 $f(1\dots n)$。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_{1\dots n}$。

输出格式

一行 $n$ 个整数表示 $f(1),f(2),\dots ,f(n)$ 的值。

样例 #1
样例输入 #1

5
1 4 2 3 5

样例输出 #1

2 5 4 5 0

【数据规模与约定】
对于 $30\%$ 的数据，$n\le 100$；

对于 $60\%$ 的数据，$n\le 5\times 10^3$ ；

对于 $100\%$ 的数据，$1\le n\le 3\times 10^6$，$1\le a_i\le 10^9$。
AC代码

#include<iostream>
#include<stack>
using namespace std;
const int Max = 3e6 + 10;

int n,arr[Max], ans[Max];
stack<int> stk;

int main() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    for (int i = n; i>=1; i--)
    {
        while (!stk.empty() && arr[stk.top()] <= arr[i]) stk.pop();
        if (!stk.empty()) ans[i] = stk.top();
        else ans[i]=0;//可不写，ans数组默认初始化全为0
        stk.push(i);
    }

    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';

    return 0;
}

单调栈总结

①遍历顺序，找某个数的左边就正序遍历，右边就倒序遍历
②及时去掉无用数据的方式，如果找小于该元素，那就出栈中所有大于等于该元素的元素，此时的栈顶就是答案（栈不为空的情况下）。
③栈中存的是元素还是元素下标。