https://ac.nowcoder.com/acm/contest/22669/A
考虑巧妙地反向遍历数组,获取一个元素之后元素地最大值,相比正序遍历,减少了遍历次数
#include <bits/stdc++.h>
#include <chrono>
using namespace std;int main() {int n;cin >> n;stack<int> s;vector<int> a(n), b(n); // 使用 vector 动态数组// 读取输入数组for (int i = 0; i < n; i++) {cin >> a[i];}if (n == 1) {// 特殊处理 n = 1 的情况cout << a[0] << endl;return 0;}// 计算 b 数组,b[i] 保存从 i 到 n-1 之间的最大值b[n-1] = a[n-1]; // 初始化最后一个值for(int i = n-2; i >= 0; i--) {b[i] = max(b[i+1], a[i]);}// 栈的出栈操作,找到字典序最大的出栈序列for(int i = 0; i < n; i++) {s.push(a[i]); // 按顺序入栈// 出栈条件:栈顶大于剩余数组中的最大值(即 b[i+1])while(!s.empty() && (i == n-1 || s.top() > b[i+1])) {cout << s.top() << " "; // 输出栈顶元素s.pop(); // 出栈}}return 0;
}