首页 > 试题广场 >

栈和排序

[编程题]栈和排序
  • 热度指数:862 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个从 1n 的排列 P,以及一个空栈。你按顺序将排列中的元素依次入栈,可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。

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

输入描述:
\hspace{15pt}在一行中输入一个整数 n \left(1 \leqq n \leqq 10^6\right)
\hspace{15pt}第二行输入 n 个整数,表示排列 P 中的元素,用空格分隔。保证给出的是一个从 1n 的排列。


输出描述:
\hspace{15pt}输出一行,包含若干整数,表示最终的出栈序列,用空格分隔,结尾不输出多余空格。
示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

入栈顺序和操作示例如下: 
\hspace{8pt}2 入栈;
\hspace{8pt}1 入栈;
\hspace{8pt}5 入栈;
\hspace{8pt}5 出栈;
\hspace{8pt}3 入栈;
\hspace{8pt}4 入栈;
\hspace{8pt}4 出栈;
\hspace{8pt}3 出栈;
\hspace{8pt}1 出栈;
\hspace{8pt}2 出栈。

备注:

这道题你会答吗?花几分钟告诉大家答案吧!