NOJ 2024 入栈序列和出栈序列 (stack)

本文主要是介绍NOJ 2024 入栈序列和出栈序列 (stack)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

入栈序列和出栈序列

描述

给出入栈序列{A}，保证{A}各个元素值各不相等，输出字典序最大的出栈序列.

如入栈序列{A} = 1, 2, 9, 4, 6, 5
则字典序最大的出栈序列为9, 6, 5, 4, 2, 1

输入

第一行一个整数n (1 <= n <= 100).
接下来是入栈序列{A}, n个正整数ai(0 < ai < 1000)，且i != j则ai != aj.

输出

一行，字典序最大的出栈序列.   每个数字以空格分开。

样例输入

6 
2 1 9 4 6 5

样例输出

9 6 5 4 1 2

提示

null

题目来源

NUPT

题目链接 :http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2024

题目分析 :从后往前找递增序列,存下每个递增序的最大值和其下标,按要求入栈出栈即可

代码 :

#include <cstdio>
#include <stack>
using namespace std;
int const MAX = 1e3 + 2;
int cur[MAX], pos[MAX], num[MAX];
stack <int> s;
int main()
{int n;scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &num[i]);//从后往前找递增序列,存下每个值和其下标for(int i = n; i > 0; i--) {if(cur[i] > num[i - 1]){cur[i - 1] = cur[i];pos[i - 1] = pos[i];}else{cur[i - 1] = num[i - 1];pos[i - 1] = i - 1;}}for(int j = 0, i = 0; i < n; i++){//栈顶元素小于未入栈的递减序，则将其入栈if(s.empty() || s.top() < cur[j]){for(int k = pos[j]; j <= k; j++)s.push(num[j]);}//由于开始从后往前找的是递增序，由先进先出的原则//先出栈的必定是当前最大的元素if(i != n - 1){printf("%d ", s.top());s.pop();}elseprintf("%d\n", s.top());}
}

这篇关于NOJ 2024 入栈序列和出栈序列 (stack)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---