题解 | 栈和排序
栈和排序
https://www.nowcoder.com/practice/b10a7ac681e9429e89a6a510e5799647
要输出出栈序列的最大字典排序：
1. 栈顶的元素 大于 所有的未入栈元素的最大值：输出栈顶到情况2
2.栈顶小于为入栈元素的最大值：
push(a[i])。
最后将所有栈中元素输出即可。
值得注意的是，这里求数组中未入栈元素的最大值时间复杂度不能过大，否则会导致不通过.
可以采取max函数从最后一个数开始预处理。
#include <iostream>
#include <stack>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
cin>>n;
vector<int> a(n);
stack<int> s;
for(int k=0;k<n;k++){
cin>>a[k];
}
vector<int> b = a;
int m[n];//对应当为第i个数入栈时，其后面未入栈元素的最大值.
m[n-1]=a[n-1];
for(int i=n-2;i>=0;i--){
m[i] = max(a[i],m[i+1]);
}
for(int i=0;i<n;i++){
if(s.empty()){
s.push(a[i]);
}else{
while(!s.empty() && s.top()>m[i]){
cout<<s.top()<<" ";
s.pop();
}
s.push(a[i]);
}
}
while(!s.empty()){
cout<<s.top()<<" ";
s.pop();
}
}
