算法简介
单调栈是在栈的基础上，保证栈内的元素是单调有序的数据结构，所以单调栈分为单调递增栈和单调递减栈。
单调递增栈：在保持栈内元素单调递增的前提下，将新元素入栈。
单调递减栈：在保持栈内元素单调递减的前提下，将新元素入栈。
时间复杂度
\(O(n)\)
实现原理
1. 单调递增栈
对于待加入的数 x，若栈顶的数为 a 且有 a > x，那么将栈顶弹出栈，重复该过程，直至栈为空或栈顶的数 a < x。
2. 单调递减栈
对于待加入的数 x，若栈顶的数为 a 且有 a < x，那么将栈顶弹出栈，重复该过程，直至栈为空或栈顶的数 a > x。
算法实例
1. 题目描述
2. AC代码
#include <bits/stdc++.h>
const int N = 100010;
int stk[N], tt;
int main() {
int n;
std::cin >> n;
while(n -- ) {
int x;
std::cin >> x;
// 不为空且栈顶比x大
while(tt && stk[tt] >= x) tt -- ;
// 判断栈是否为空
if(!tt) std::cout << "-1 ";
else std::cout << stk[tt] << ' ';
// 将当前数入栈
stk[++ tt] = x;
}
return 0;
}