首页 > 试题广场 >

栈和排序

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

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

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


输出描述:
\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 出栈。

备注:

算法知识视频讲解
添加回答

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

提交观点

问题信息

上传者：牛客301599号
难度：
0条回答 4331浏览

热门推荐

通过挑战的用户

查看代码

相关试题

栈和排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号