栈和排序 1.用a数组记录入栈的顺序
2.用maxx数组记录大于等于a[i]且在i后面的数的最大值
3.用一个stack栈s枚举压栈出栈的过程
4.用res数组记录最终的出栈顺序
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 10), maxx(n + 10), res;
// 记录入栈的顺序
for(int i = 0 ; i < n ; i ++ )
cin >> a[i];
maxx[n - 1] = a[n - 1]; // 比a[n - 1]大的数是他自己
// 用maxx数组记录大于等于a[i]的数的值
for(int i = n - 2 ; i >= 0 ; i -- )
maxx[i] = max(maxx[i + 1], a[i]);
stack<int> s;
// 枚举入栈压栈的顺序
for(int i = 0 ; i < n ; i ++ )
{
s.push(a[i]); // 压栈
// 如果栈非空,并且栈顶元素比右边那个的右侧最大值还大的话
// 说明已经找到剩余序列中的最大值了,即可记录res出栈
while(s.size() && s.top() >= maxx[i + 1])
{
res.push_back(s.top());
s.pop();
}
}
for(int i = 0 ; i < n ; i ++ )
cout << res[i] << ' ';
return 0;
}