栈和排序（字典序最大的出栈序列）

链接：https://ac.nowcoder.com/acm/problem/14893
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

给你一个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出栈

要让字典序最大就要让大的数尽量先出栈。

用一个数组rmax[i]表示第 i 项到第 n 项的数的最大值。

如果栈顶元索大于第i项到第n项的最大值，那么直接让这个元索出栈，让大的先出栈总能保证字典序最大。

如果栈顶元素小于第 i 项到第 n 项的最大值，那就让该元素入栈，等着后面更大的元素。

如果最后所有元素都已经入栈了，记得还要输出栈内剩余的元素。

代码如下：

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 #define mst(a) memset(a,0,sizeof(a))
 5 const int INF = 0x3f3f3f3f;
 6 const double eps = 1e-8;
 7 const int mod = 1e9+7;
 8 const int maxn = 1e6+10;
 9 using namespace std;
10 
11 int a[maxn];
12 int rmax[maxn];
13 stack<int> sk;
14 vector<int> vt;
15 
16 int main()
17 {
18     #ifdef DEBUG
19     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
20     #endif
21     
22     int n;
23     scanf("%d",&n);
24     for(int i=1;i<=n;i++)
25         scanf("%d",&a[i]);
26     for(int i=n;i>=1;i--)
27         rmax[i] = max(a[i],rmax[i+1]);
28     for(int i=1;i<=n;i++)
29     {
30         while(!sk.empty()&&sk.top()>=rmax[i])
31         {
32             vt.push_back(sk.top());
33             sk.pop();
34         }
35         sk.push(a[i]);
36     }
37     while(!sk.empty())
38     {
39         vt.push_back(sk.top());
40         sk.pop();
41     }
42     for(int i=0;i<vt.size();i++)
43         printf(i==vt.size()-1? "%d
":"%d ",vt[i]);
44     
45     return 0;
46 }

把第一次wa的思路和代码粘下：

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 #define pb push_back
 4 #define mst(a) memset(a,0,sizeof(a))
 5 const int INF = 0x3f3f3f3f;
 6 const double eps = 1e-8;
 7 const int mod = 1e9+7;
 8 const int maxn = 1e5+10;
 9 using namespace std;
10 
11 stack<int> sk;
12 vector<int> vt;
13 
14 int main()
15 {
16     #ifdef DEBUG
17     freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
18     #endif
19     
20     int n;
21     scanf("%d",&n);
22     int MAX=n;
23     for(int i=1;i<=n;i++)
24     {
25         int x;
26         scanf("%d",&x);
27         if(x!=MAX)
28         {
29             sk.push(x);
30             continue;
31         }
32         vt.push_back(x);
33         MAX--;
34         while(!sk.empty()&&sk.top()==MAX)
35         {
36             vt.push_back(sk.top());
37             sk.pop();
38             MAX--;
39         }
40     }
41     while(!sk.empty())
42     {
43         vt.push_back(sk.top());
44         sk.pop();
45     }
46     for(int i=0;i<vt.size();i++)
47         printf(i==vt.size()-1? "%d
":"%d ",vt[i]);
48     
49     return 0;
50 }

这种做法hack数据：

1 4 3 5 2

正确答案：5 3 4 2 1，上述输出：5 2 3 4 1