单调栈
传送门
模板题，背过即可
题目
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
输入格式
第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。
输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。
数据范围
1 ≤ N ≤ 105
1 ≤ a [ i ] ≤ 109
实现代码
数组模拟栈， t t 栈顶指针。
#include <iostream> #include <stack> using namespace std; const int N = 100010; int a[N], n; int s[N], tt; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { while(i && s[tt] >= a[i]) tt--; if(tt) cout << s[tt] << ' '; else cout << -1 << ' '; s[++tt] = a[i]; } return 0; }
stack
#include <iostream> #include <stack> using namespace std; const int N = 100010; stack<int> s; int a[N], n; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { while(!s.empty() && a[s.top()] >= a[i]) s.pop(); if(!s.empty()) cout << a[s.top()] << ' '; else cout << -1 << ' '; s.push(i); } return 0; }
