单调栈¶
前置知识¶
数组，数组实现栈
目标¶
单调栈模板题
What¶
单调栈，能以O(n)的时间复杂度，找到每一个元素右边第一个比他大/小的数字（就是把这个数字挤出栈的数字）。同理，也可以这样解释，找到每个数左边离它最近的比它大/小的数
单调栈插入过程，示范，点击“单调栈”访问链接
How¶
题意：给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1 思考： 1、先考虑暴力怎么做 2、然后想一些性质，把目光集中在比较少的状态里（构造单调性） 3、从而把问题的复杂度降低
// 核心代码示范
// 求左边第一个比它小的数
while (tt && stk[tt] >= x) tt--; // 栈顶stk[tt]如果大于等于当前值x，那么弹出栈顶
if (tt) cout << stk[tt] << ' '; // 这个时候栈顶如果存在，那么栈顶就是当前顶一个比x小的值
else cout << -1 << ' ';
// 完整代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int stk[N], tt;
int main()
{
cin >> n;
while (n--)
{
int x;
cin >> x;
while (tt && stk[tt] >= x) tt--;
if (tt) cout << stk[tt] << ' ';
else cout << "-1" << ' ';
stk[++tt] = x;
}
puts("");
return 0;
}
题单¶
总结¶
提高组入门算法