栈和排序

栈和排序

给你一个1~n的排列和一个栈，入栈顺序给定
你要在不打乱入栈顺序的情况下，对数组进行从大到小排序
当无法完全排序时，请输出字典序最大的出栈序列

输入样例：

5
2 1 5 3 4

输出样例：

5 4 3 1 2

思路

如果要字典序最大，那么我们肯定要尽可能的按n~1的顺序输出，但是入栈，出栈顺序不可能是随意的，看样例，我们开始找到最大的那个数，出栈，出栈之后栈顶的元素依然比后面的所有元素还要大时，应该继续出栈，如果小于则入栈。再来看一组数据

10
1 2 3 4 5 6 8 9 10 7

这组数据我们可以发现，10出栈之后9,8也要继续出栈，直到栈顶的元素比后面所有的还要小时继续入栈。大于等于都要出栈。所以我们可以用一个数组，mx[i]表示i~n ，a[i]中最大的数。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
#define debug(x) cout << #x << ": " << x << endl;
#define MAXN 100005
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }

stack<int> st;
vector<int>ans;

int n,x;
int mx[N],a[N];


int main(){
//    freopen("in.txt", "r", stdin);
//     freopen("test.txt", "w", stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=n;i>0;i--) mx[i]=max(mx[i+1],a[i]);
    for(int i=1;i<=n;i++){
        while(!st.empty()&&st.top()>mx[i]){
            cout<<st.top()<<" ";
            st.pop();
        }
        st.push(a[i]);
    }
    while(!st.empty()){
        cout<<st.top()<<" ";
        st.pop();
    }
    return 0;
}