首页 > 代码库 > 济南学习 Day1 T2 pm
济南学习 Day1 T2 pm
【问题描述】
栈是一种强大的数据结构,它的一种特殊功能是对数组进行排序。例如,借
助一个栈,依次将数组 1,3,2 按顺序入栈或出栈,可对其从大到小排序:
1 入栈;3 入栈;3 出栈;2 入栈;2 出栈;1 出栈。
在上面这个例子中,出栈序列是 3,2,1,因此实现了对数组的排序。
遗憾的是,有些时候,仅仅借助一个栈,不能实现对数组的完全排序。例如
给定数组 2,1,3,借助一个栈,能获得的字典序最大的出栈序列是 3,1,2:
2 入栈;1 入栈;3 入栈;3 出栈;1 出栈;2 出栈。
请你借助一个栈,对一个给定的数组按照出栈顺序进行从大到小排序。当无
法完全排序时,请输出字典序最大的出栈序列。
【输入格式】
输入共2行。
第一一个整数N,表示入栈序列长度。
第二行包含N个整数,表示入栈序列。输入数据保证给定的序列是1到 N 的全
排列,即不会出现重复数字。
【输出格式】
仅一行,共N个整数,表示你计算出的出栈序列。
【样例输入】
3
2 1 3
【样例输出】
3 1 2
【样例解释】
这回山里有座塔。
【数据规模与约定】
3 3 。
60%的数据,1 ≤ N ≤ 10 ^5 。
对于100%的数据,1 ≤ N ≤ 10 ^6 。
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<stack>
5 #define MAXN 100000
6 using namespace std;
7 int q[MAXN];
8 int a[MAXN],n,vis[MAXN],team;
9 int main()
10 {
11 scanf("%d",&n);
12 for(int i=1;i<=n;i++)
13 scanf("%d",&a[i]);
14 int k=n,head=1;
15 while(k)
16 {
17 while(vis[k]) k--;
18 if(k==0)
19 {
20 for(int i=team;i>=1;i--)
21 printf("%d ",q[i]);
22
23 return 0;
24 }
25 while(q[team]>k)
26 {
27 printf("%d ",q[team]);
28 team--;
29 }
30 while(a[head]!=k)
31 {
32 q[++team]=a[head];
33 vis[a[head]]=true;
34 head++;
35 }
36 printf("%d ",a[head]);
37 head++;k--;
38 }
39 return 0;
40 }
思路:首先贪心最大的肯定要排在第一个,即最大的之前的要全部push,接下来肯定是N-1这个数最大,如果他没有进栈,那么一直push到它进栈,如果它已经进栈,那么比较栈顶与要进栈的最大数比较最大的输出。后面最大的数直接用while判断是否进栈即可。代码是手写的栈
济南学习 Day1 T2 pm
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。