浅析栈排序与栈

## 一、首先要先介绍栈 这个地方笔者就不多啰嗦了，想必大家都应该清楚吧——栈是一种线性表，特点是先进后出。通常的应用不是特别广泛，但也不算生僻：例如电脑中的信息存储就会用到栈——可以随时处理最近新增的信息，做到时间处理单调；或者用于存储表达式（此处便是因为其独特的性质，读者可以思考一下原因） ## 二、然后再说题目吧——栈排序 看到这儿，你该知道，这不是某一年的noip“双栈排序”，而是“栈排序”，看错题的同学现在走也不迟啊（主要是洛谷上没有） 题目： 【问题描述】 栈是一种强大的数据结构，它的一种特殊功能是对数组进行排序。例如，借 助一个栈，依次将数组 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 样例就不解释了。。。 【笔者浅析】//敲黑板划重点 10分做法：枚举每一种情况，然后排序。 ps:这样你就成功地把这个题做成了一道码力题。。。并且期望得分10分（大佬可以得三十分，不过既然是大佬怎么可能暴力呢qwq） 30分做法：不会 60分做法：同上 满分做法： 事先说明，笔者并没有发现保有这道题的OJ。。所谓满分做法是和大佬的标程对拍了半个多小时之后都没有差错才得出的满分结论，如果卡常不能怨我qwq（逃 ## 三、终于要说正事了 【笔者浅析2qwq】 首先我们要知道，字典序最大的意义是什么——从头开始比较，一直按位比较，直到某个串的字符的ascll码更大，此字符串整体字典序便较大。知道这个之后，我们便可以很简单的想出贪心策略：第一次一定要选字典序最大的元素出栈（O（n）筛一遍即可）,当然，此时该元素之前的所有元素只能顺序入栈（因为不能出栈，所以只能顺序入栈）；之后呢？之后便是选择次大的 元素作为第二位——但此时我们可选择的方案只有两种： 1、将栈顶元素出栈 2、将未入栈的元素中最大的元素出栈，即继续入栈直到最大值出现（可以直接被操作）。 但是我们可以如是想：操作2中，我们要将未入栈的元素中最大的元素出栈，其实也可以等价于将这个次大的元素之前的所有元素入栈后，将次大的元素入栈然后立即让其出栈，这便达到了出栈字典序最大。 在之后呢？也是有两种情况： 1、所有元素要么在栈中，要么被弹出栈：此时只需要按顺序弹出栈顶元素即可，毕竟你也没办法改变顺序啊qwq 2、仍有元素未入栈且未被弹出过：我们可以用迭代的思想或者怎样：这些元素早晚都会入栈，所以执行到这一步并不会导致新的状态，只需要 继续入栈——>比较最大——>出栈 即可。所以啦，无论如何人都只会有状态1（上文）啦。。。~~两种情况是坑你的了~~ ------------ 【代码实现方面】 1、我们为了判断该弹出栈顶元素还是继续入栈时，可以考虑用栈顶元素和此时的后缀中的最大值来判断，所以一开始需要维护初始串的后缀和哇。（应该比较好想，一笔带过吧） 2、在将未入栈的元素入栈时，我们不好掌控剩余串的长度，此时我选择倒序存一个数组，不正序存储是因为不好确定长度 ~~（其实就是闲的）~~，然后size--即可（sizen是因为size会重名。。。虽然这个题并不会） 3、码风清奇，不喜勿喷~~（我明明是最棒的）~~ 4、stl大法好emmmmmmmm 贴代码 ```cpp #include<iostream> #include<stack> using namespace std; stack<int>zhan; int stackn[100001],big[100001],ss[100001]; //依次为原数组、后缀最大值、倒序数组 int main() { int now,n,maxn=-1; cin>>n; for(int i=1;i<=n;i++) { cin>>stackn[i]; if(maxn<stackn[i]) {maxn=stackn[i]; now=i;} } for(int i=1;i<=n;i++)ss[i]=stackn[n-i]; cout<<maxn<<" "; for(int i=1;i<=n;i++) big[n-i]=max(big[n-i+1],stackn[n-i]);//维护后缀最大值 for(int i=1;i<now;i++)zhan.push(stackn[i]); int sizen=n-now; while(sizen) { if(zhan.top()<big[n-sizen]){zhan.push(ss[sizen]);sizen--;} else {cout<<zhan.top()<<" ";zhan.pop();} } while(!zhan.empty()) { cout<<zhan.top()<<" "; zhan.pop(); } return 0; } ```