单调栈

单调栈（题目连接）

分析

根据样例： 3 4 2 7 5 若2存在，则前面的3 4永远不可能作为答案输出，所以在栈中删掉即可 基于这种思想，即可在栈中得到单调上升的序列

代码

使用vis做栈

#include <bits/stdc++.h> using namespace std; typedef long long ll; stack<int> vis; int main() { int n; scanf("%d", &n); while (n--) { int x; scanf("%d", &x); if (vis.size() == 0) { vis.push(x); cout << "-1" << " "; } else if (vis.top() < x) { int res = vis.top(); vis.push(x); cout << res << " "; } else { while (vis.size() > 0) { if (vis.top() >= x) vis.pop(); else break; } if (vis.size() == 0) { cout << "-1" << " "; vis.push(x); } else { int res = vis.top(); vis.push(x); cout << res << " "; } } } return 0; }

数组模拟栈（代码相对较短）

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int vis[N], top; // 这里默认栈顶指针初始值为0,即栈顶指针指向栈顶元素 int main() { int n; cin >> n; while (n--) { int x; scanf("%d", &x); while (top && vis[top] >= x) { top--; } if (!top) printf("-1 "); else printf("%d ", vis[top]); vis[++top] = x; } return 0; }