我要招人

去企业版

首页 > 试题广场 >

栈和排序

[编程题]栈和排序

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

给你一个1->n的排列和一个栈，入栈顺序给定

你要在不打乱入栈顺序的情况下，对数组进行从大到小排序

当无法完全排序时，请输出字典序最大的出栈序列

输入描述:

第一行一个数n
第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格

输出描述:

输出一行n个数表示答案，用空格隔开，结尾无空格

示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

2入栈；1入栈；5入栈；5出栈；3入栈；4入栈；4出栈；3出栈；1出栈；2出栈

算法知识视频讲解

ThinkofBlank

发表于 2020-05-19 22:28:57

一个简单的贪心做法（已通过@7QQQQQQQ大佬的hack数据）我们设maxe[i]表示i-n的元素的最大值。那么，我们假设，当前栈顶的元素比maxe[i+1]大（最近入栈的是第i个元素），那么，不难发现，如果我们当前元素不出栈的话，之后如果有元素入栈，那么最后出栈的字典序一定会小于当前元素出栈展开全文

HGDB

发表于 2020-05-29 13:18:51

思路要让字典序最大很明显就要让更大的那个数先出栈。我这里用了一个数组表示第i项到第n项的数的最大值。如果栈顶元素大于第i项到第n项的最大值，说明如果让这个元素出栈此时的字典序肯定会更大。如果栈顶元素小于第i项到第n项的最大值，那就让该元素入栈，因为让大的先出栈总总能保证字典序最大展开全文

ziuch

发表于 2020-08-21 21:47:39

题目描述给你一个1->n的排列和一个栈，入栈顺序给定你要在不打乱入栈顺序的情况下，对数组进行从大到小排序当无法完全排序时，请输出字典序最大的出栈序列输入描述: 第一行一个数n 第展开全文

Acapplella

发表于 2020-05-20 11:48:48

题目描述:给你一个1->n的排列和一个栈，入栈顺序给定你要在不打乱入栈顺序的情况下，对数组进行从大到小排序当无法完全排序时，请输出字典序最大的出栈序列输入描述: 第一行一个数n 第二行n个数，表示入栈的顺序，用空格隔开，结尾无空格输出描述: 输出一行n个数表示答案，用空格隔开，结尾无空格具体思展开全文

客户端劝退第四人

发表于 2020-05-18 18:08:58

此题从n,n-1....开始出栈（前提是能够出） #include<iostream> #include<stack> #include<algorithm> #include<vector> using namespace std; const in 展开全文

牛客764138432号

发表于 2021-03-13 23:59:24

发一个java版本的 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); in 展开全文

usx21145328

发表于 2022-02-06 11:51:12

思路：在a数组中，如果a[i]后面没有比它还大的数，那就直接把这个数输出,否则这个位置输出的数就会比a[i]小，那么字典序就会更小。用一个数组maxn来记录每个数后面的最大值，从后往前循环，求出a[i]到a[n]的最大值代码： #include<bits/stdc++.h> u 展开全文

菜鸡要上街

发表于 2020-06-07 09:10:48

链接：https://ac.nowcoder.com/acm/problem/14893来源：牛客网给你一个1->n的排列和一个栈，入栈顺序给定你要在不打乱入栈顺序的情况下，对数组进行从大到小排序当无法完全排序时，请输出字典序最大的出栈序列用例输入 5 2 1 5 3 4输出 5 4 3 展开全文

青春不悔

发表于 2020-05-30 13:39:24

include<bits/stdc++.h> using namespace std;stack<int>q;int n,t,m,i;int main() { cin >> n; for (i = 0,m=n; i < n; i++) { 展开全文

hhuggo

发表于 2024-04-23 18:27:43

https://ac.nowcoder.com/acm/problem/14893 说一下这题用树状数组的解法树状数组是比较暴力直观的想法，也是我读完题的第一个想法。它不是最好的解法第一步，贪心思想首先还是贪心的思想，对于每一次入栈之后，设t为栈顶元素，那么就要判断这个时候取t是不是最优解，如展开全文