数据结构与算法（c++）|【19. 单调栈】 c++|数据结构|算法

单调栈用途：主要找到每个数左边离他最近的且比它小的数在什么地方(或者找到每个数右边离他最近的且比它大的数在什么地方)

题目给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 ?1。
输入格式第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式 【数据结构与算法（c++）|【19. 单调栈】】共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 ?1。
数据范围 1≤ N ≤ 105
1≤ 数列中元素 ≤ 109
输入样例：
5 3 4 2 7 5

输出样例：
-1 3 -1 2 2

方法一：暴力解法

for (int i = 0; i < n; i ++) for (int j = i - 1; j >= 0; j --) if (a[i] > a[j]) { cout << a[j] << endl; break; }

#include using namespace std; const int N = 100010; int q[N]; int n; int main() { cin >> n; for (int i = 0; i < n; i ++)cin >> q[i]; for (int i = 0; i < n; i ++) { int j = i - 1; for (; j >= 0; j --) { if (q[j] < q[i]) { cout << q[j]<<" "; break; }} if (j < 0) { cout << "-1" <<" "; } } return 0; }

方法二：优化

用栈存储 i 左边的元素
如果 ax >= ay,并且x < y那么ax永远不会输出，就直接可以删除。(只要有这种逆序的关系，前面的数就会被删掉，此时剩下的序列就是单调序列了)

#include using namespace std; const int N = 100010; 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; //cout << tt << endl; ; } return 0; }