题解 | 栈和排序
栈和排序
https://www.nowcoder.com/practice/b10a7ac681e9429e89a6a510e5799647
#include <bits/stdc++.h>
using ll = long long ;
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define vii vector<vector<ll>>
#define fi first
#define se second
#define vs vector<string>
#define eb emplace_back
#define in insert
#define pf push_front
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); i++)
const int inf = 2e18 + 9 ;
const int mod1 = 1e9 + 7 ;
const int mod2 = 998244353 ;
typedef pair<int, int> pll;
typedef long double db;
inline ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;};
inline int read(){int x = 0;short f = 1;char c = getchar();while ((c < '0' || c > '9') && c != '-')c = getchar();if (c == '-')f = -1, c = getchar();while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();x *= f;return x;}
inline ll qsm(ll a , ll b){ll res = 1 ; while(b){if(b & 1){res *= a ; }b >>= 1 ; a *= a ; }return res ; }
int dir[4][2] = {{1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1}};
int dirx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int diry[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void work()
{
int n ; cin >> n ;
int j = 0 ;
vi a(n) ;
for(int i = 0 ; i < n ; i++)
{
cin >> a[i] ;
}
vi b = a ;
sort(all(b) , greater()) ;
stack<int>q ;
vi ans ;
for(int i = 0 ; i < n ; i++)
{
if(a[i] == b[j])
{
ans.pb(a[i]) ;
j++ ;
while(q.top() == b[j])
{
ans.pb(q.top()) ;
q.pop() ;
j++ ;
}
}
else
{
q.push(a[i]) ;
}
}
if(j != n - 1)
{
while(q.size())
{
ans.pb(q.top()) ;
q.pop() ;
}
}
for(int i : ans)
{
cout << i << " " ;
}
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
work();
}
return 0;
}