首页 > 代码库 > 栈排序

栈排序

【问题描述】
栈是一种强大的数据结构,它的一种特殊功能是对数组进行排序。例如,借
助一个栈,依次将数组 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行。

第一一个整数?,表示入栈序列长度。
第二行包含?个整数, 表示入栈序列。 输入数据保证给定的序列是1到 n 的全
排列,即不会出现重复数字。
【输出格式】


仅一行,共?个整数,表示你计算出的出栈序列。


【样例输入】


3
2 1 3


【样例输出】


3 1 2


【样例解释】


这回山里有座塔,钟神的塔;


【数据规模与约定】


3 3 。

60%的数据,1 ≤ ? ≤ 10 5 。
对于100%的数据,1 ≤ ? ≤ 10 6

 

思路:

  栈排序,不一定像sort一样完全有序,只能尽量输出最大

  所以,我们用贪心策略;

  维护一个后缀最大值,然后每入栈到最大后缀的元素

  如果后缀值小于栈顶元素,则出栈(输出);

 上代码:

#include<cstdio>
#include<algorithm>

using namespace std;

int n,a[1000001],zhan[1000005];
int sum[1000001],jkl,head=0,tail=0;

char ch;

void qread(int &x)
{
    x=0,jkl=1;ch=getchar();
    while(ch>9||ch<0){if(ch==-)jkl=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+(int)(ch-0);ch=getchar();}
    x*=jkl;
}

int main()
{
    qread(n);
    for(int i=1;i<=n;i++) qread(a[i]);
    sum[n]=a[n];
    for(int i=n-1;i>=1;i--) sum[i]=max(sum[i+1],a[i]);
    zhan[++head]=a[++tail];
    tail++;
    while(1)
    {
        if(sum[tail]>zhan[head]||!head)
        for(int i=tail;i<=n;i++)
        if(a[i]!=sum[tail]) zhan[++head]=a[i];
        else
        {
            tail=i+1;
            printf("%d ",a[i]);
            break;
        }
        else
        {
            printf("%d ",zhan[head--]);
        }
        if(tail>n) break;
    }
    while(head--) printf("%d ",zhan[head+1]);
    return 0;
}

 

栈排序