鏈接：https://ac.nowcoder.com/acm/problem/14893
來源：牛客網

題目描述
給你一個1->n的排列和一個棧，入棧順序給定
你要在不打亂入棧順序的情況下，對數組進行從大到小排序
當無法完全排序時，請輸出字典序最大的出棧序列
輸入描述:
第一行一個數n
第二行n個數，表示入棧的順序，用空格隔開，結尾無空格
輸出描述:
輸出一行n個數表示答案，用空格隔開，結尾無空格
示例1
輸入
復制
5
2 1 5 3 4
輸出
復制
5 4 3 1 2
說明
2入棧；1入棧；5入棧；5出棧；3入棧；4入棧；4出棧；3出棧；1出棧；2出棧
思路:對于數a[i]，如果說它等于[i,n]之間的最大值，那么它就可以優先輸出。如果說不等于的話，就說明[i,n]之間有比a[i]大的數字，那么就將a[i]保留下來。假如a[i]符合第一種情況，而保留的那個數組中第一個數x，大于a[i+1]的話，說明[i+1,n]沒有比x大的了，這個時候要先輸出x。

代碼如下（用stack應該更好一些，這個題目我用的vector）：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; vector<int> p1,p2,p3; int a[maxx]; int n;int main() {scanf("%d",&n);int x;p1.push_back(0);for(int i=1;i<=n;i++) {scanf("%d",&x);p1.push_back(x);}a[n+1]=0;for(int i=n;i>=1;i--) a[i]=max(a[i+1],p1[i]);p3.push_back(0);for(int i=1;i<=n;i++){if(a[i]!=p1[i]) p2.push_back(p1[i]);else{p3.push_back(p1[i]);if(i+1<=n){while(p2.size()&&p2.back()>a[i+1]) p3.push_back(p2.back()),p2.pop_back();}}}while(p2.size()) p3.push_back(p2.back()),p2.pop_back();for(int i=1;i<=n;i++) cout<<p3[i]<<" ";return 0; }

努力加油a啊，(^o)/~

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的栈和排序(贪心+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。