栈和排序

思路

要让字典序最大很明显就要让更大的那个数先出栈。

我这里用了一个数组 表示第i项到第n项的数的最大值。

1. 如果栈顶元素大于 第i项到第n项的最大值，说明如果让这个元素出栈此时的字典序肯定会更大。
2. 如果栈顶元素小于 第i项到第n项的最大值，那就让该元素入栈，因为让大的先出栈总总能保证字典序最大

如果所有元素都已经入栈了，那记得输出栈内剩余的元素

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[1000005],pos[1000005];
stack<int> q;
int main(){
    int n = read();
    for(int i = 1 ; i <= n ; ++i) a[i] = read();
    for(int i = n ; i > 0 ; --i) pos[i] = max(pos[i+1],a[i]);
    for(int i = 1 ; i <= n ; ++i){
        if(q.empty()) q.push(a[i]);
        else{
            if(q.top() < pos[i]) q.push(a[i]);
            else {
                cout<<q.top()<<" ";
                q.pop();
                i--;//弹出后的栈头也可能比a[i]来的大，这里回退
            }
        }
    }
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
}

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
#define stop system("pause")
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int a[1000005],pos[1000005];
stack<int> q;
int main(){
    int n = read();
    for(int i = 1 ; i <= n ; ++i) a[i] = read();
    for(int i = n ; i > 0 ; --i) pos[i] = max(pos[i+1],a[i]);
    for(int i = 1 ; i <= n ; ++i){
        while(!q.empty() && q.top() > pos[i]){
              cout<<q.top()<<" ";
              q.pop();
         }
        q.push(a[i]);
    }
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
}