[单调栈+模板] 单调栈模板

文章目录

0. 前言1. 单调栈

0. 前言

Biu

单调栈主要用于求取左边第一个比它大，或者比它小的数。

就比如站队随便排成一列，可以求到每个人后面第一个比他高的人。

同理可以推广至右边，比它矮均可。这就是单调递增栈、递减栈，从前至后入栈，从后向前入栈的区别了。

单调栈比较抽象，非常具有智慧的想法，可应用的场景相当少，根据几个经典题目体会它的用法会极大的帮助理解。手动模拟一遍数据就能够完全理解了。

1. 单调栈

这里是拿数组模拟栈。

模板代码：

#include <iostream> using namespace std; const int N = 1e5+5; int n; int stk[N], tt; int main() { cin >> n; for (int i = 0; i < n; ++i) { int x; cin >> x; while (tt && stk[tt] >= x) tt--; if (tt) cout << stk[tt] << ' '; else cout << -1 << ' '; stk[++tt] = x; } return 0; }