简介
单调栈和单调队列都是思维难度比较大的数据结构，但是比较幸运，这些数据结构能出的题不多，只有几个板子。
要理解单调栈，首先得明白“单调”是只它存储的内容单调，不是说它有多简单（不过代码实现确实简单）。
实现
模板题（AcWing.830）
题目描述：
给定一个长度为 \(N\) 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 \(−1\)。
样例
in：
5
3 4 2 7 5
out:
-1 3 -1 2 2
单调栈实现
首先想暴力做法（毕竟暴力是灵感的源泉），就是每个数往左遍历，直到找到比它小的数，就输出。
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),a[N];
int main()
{
for(ll i=1;i<=n;i++)
{
a[i]=read();
if(i==1)
{
putchar('-');
putchar('1');
putchar(' ');
}
for(ll j=i-1;j>=1;j--)
{
if(a[j]<a[i])
{
write(a[j]),putchar(' ');
break;
}
if(j==1&&a[j]>=a[i])
{
putchar('-');
putchar('1');
putchar(' ');
}
}
}
return 0;
}
打完暴力，想想有什么可以优化的地方。
这些数可以看做一个栈，每次输入的数是 \(x\)，然后就把栈内元素一个一个弹出，直到找到第一个小于 \(x\) 的数，然后把它输出，如果栈空了还没有答案，就输出 -1 。
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}//卡常
ll n=read(),top,stk[N];
int main()
{
while(n--)
{
ll x=read();
while(top&&stk[top]>=x) top--;
if(top) write(stk[top]),putchar(' ');
else putchar('-'),putchar('1'),putchar(' ');
stk[++top]=x;
}
return 0;
}