一、简述
本节介绍一下单调栈以及单调栈的一些应用。
二、单调栈
所谓单调栈，就是具有存储的元素呈现某种单调性的栈。
比如：从栈底元素到栈顶元素是单调递减的，就是一个单调递减栈。
下面我们引入几道题目来更好的理解一下。
三、例题
1.[AcWing830.单调栈]
题目描述
给定一个长度为 \(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
解题思路
既然是介绍单调栈，那么我们肯定是使用单调栈来解决。具体思路：我们要输出每个数左边第一个小于它自己的数，我们构造一个单调单调递增的栈，首先我们从左往右遍历序列，当栈不空的时候，我们比较栈顶元素和当前数 \(a_i\) 的大小，如果栈顶元素大于等于 \(a_i\)，我们就弹出栈顶，直至栈为空或者不再满足为止，如果栈为空，说明 \(i\) 之前没有元素小于 \(a_i\)，就输出 \(-1\)，如果栈中还有元素，那当前的栈顶就是 \(i\) 左边第一个小于 \(a_i\) 的数。然后我们将 \(a_i\) 加到栈顶。
C++代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, tt;
int stk[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
int x;
scanf("%d", &x);
while(stk[tt] >= x && tt) tt --;
if(tt == 0)
printf("-1 ");
else
printf("%d ", stk[tt]);
stk[++ tt] = x;
}
return 0;
}
2.[Daimayuan Online Judge.最大矩形面积]
题目描述
有一张 \(n\) 列的网格图，每列有一些格子被小蜗从底向上涂了色。现在给你每一列被涂色的格子的高度 \(a_i\)，请你求出被涂色的格子组成的最大矩形的面积。
输入格式
第一行一个整数 \(n\)，表示总列数。
接下来一行 \(n\) 个数 \(a_1,a_2,...,a_n\)。
输出格式
输出一行一个数，表示最大面积。
数据范围
对于 \(100\%\) 的数据，保证 \(1≤n≤2×10^5,1≤a_i≤10^9\)。
输入样例
5
1 2 5 3 4
输出样例
9
解题思路
具体思路：我们对于每一个 \(a_i\)，往其左边和右边找到小于 \(a_i\) 的第一个数所在的位置，分别是 \(l_i\) 和 \(r_i\)。那么对于这之间的矩形面积为 \((r_i - l_i - 1)*{a_i}\)。然后我们对于所有的矩形面积求最大值即可。
比如样例：对于 \(a_1,...,a_5\)，分别形成的矩形面积为 \(5、8、5、9、4\)，在枚举的时候我们可以看到其正确性：首先是尽可能往两边延伸，且可以覆盖在 \(a_i\) 情况下的最大面积。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, a[N], stk[N], tt = 0;
int l[N], r[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++)
{
while (tt && a[i] <= a[stk[tt]])
tt --;
if (tt)
l[i] = stk[tt];
else
l[i] = 0;
stk[++ tt] = i;
}
tt = 0;
for (int i = n; i >= 1; i --)
{
while (tt && a[i] <= a[stk[tt]])
tt --;
if (tt)
r[i] = stk[tt];
else
r[i] = n + 1;
stk[++ tt] = i;
}
long long ans = 0;
for (int i = 1; i <= n; i ++)
ans = max(ans, 1ll * abs(r[i] - l[i] - 1) * a[i]);
cout << ans;
return 0;
}