首页 > 试题广场 >

栈和排序

[编程题]栈和排序

热度指数：5901 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个从 $1$ 到 $n$ 的排列 $P$ ，以及一个空栈。你按顺序将排列中的元素依次入栈，可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。

$\hspace{15pt}$ 理想情况下，你想得到一个严格从大到小排序的输出序列 $n, n-1, \dots,1$ ，但受栈操作限制可能无法实现。当无法完全排序时，请输出**字典序**最大的合法出栈序列。

输入描述:

在一行中输入一个整数  。 
第二行输入  个整数，表示排列  中的元素，用空格分隔。保证给出的是一个从  到  的排列。

输出描述:

输出一行，包含若干整数，表示最终的出栈序列，用空格分隔，结尾不输出多余空格。

示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

入栈顺序和操作示例如下： 
2 入栈； 
1 入栈； 
5 入栈； 
5 出栈； 
3 入栈； 
4 入栈； 
4 出栈； 
3 出栈； 
1 出栈； 
2 出栈。

备注:

算法知识视频讲解

Python 3

小比特大梦想

我这里提供一个比较简单的方法：

先找到列表中的最大元素，再依次遍历列表，遇到最大的元素就放到输出列表里面，再将这个最大值从原列表中去除（其实不是从真正的原列表中去除，因为我们for循环遍历的列表不能被改变，所以我们先复制一个列表l，找最大值就从列表l中找）。

n=int(input())
p=list(map(int,input().split()))
l=p[:]
stack=[]
output=[]
max=sorted(l)[-1]
for i in p:
    if i==max:
        output.append(i)
        l.remove(i)
        max=sorted(l)[-1]
    else:
        stack.append(i)
for j in range(len(stack)):
    output.append(stack.pop(-1))
print(' '.join(map(str,output)))

发表于 2026-01-14 00:04:42 回复(0)