首页 > 试题广场 >

栈和排序

[编程题]栈和排序
  • 热度指数：3230 时间限制：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 出栈。

备注:

算法知识视频讲解
查看答案及解析
添加回答
C/C++
KBing头像 KBing 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; i++)
        cin >> v[i];

    vector<int> biggest(n, v[n-1]);
    for(int i = n-2; i >= 0; i--)
        biggest[i] = max(biggest[i+1], v[i]);

    vector<int> ans;
    stack<int> s;

    for(int i = 0; i < n; i++) {
        s.push(v[i]);
        while(!s.empty() && s.top() > biggest[i+1]) {
            ans.push_back(s.top());
            s.pop();
        }
    }
    while(!s.empty()) {
        ans.push_back(s.top());
        s.pop();
    }
    for(auto &num : ans)
        cout << num << " ";
    cout << endl;
    return 0; 
}
发表于 2021-03-29 17:01:36 回复(0)
Python3
意若久时天然呆头像 意若久时天然呆
def out_maxstack(maxnum: int, stack: list[int]) -> str:
    t, out = [], []
    for i in stack:
        t.append(i)
        while t and t[-1] == maxnum:
            out.append(t.pop())
            maxnum -= 1
    while t:
        out.append(t.pop())
    return " ".join(map(str, out))

if __name__ == "__main__":
    n, p = int(input().strip()), list(map(int, input().strip().split(" ")))
    print(out_maxstack(n, p))
发表于 2025-11-21 11:01:33 回复(0)
C++
牛客229517627号头像 牛客229517627号
提供一个占用内存极少，但时间占用略多的方法
#include <iostream>
#include <vector>
using namespace std;

int main(){
int n;
cin>>n;

int flag=n;
bool isfirstoutput=true;
vector<int> nums;
nums.reserve(n);

for(int i=0;i<n;++i){
    int current;
    cin>>current;

    if(current==flag){
        --flag;
        cout<<(isfirstoutput ? "" : " ")<<current;
        isfirstoutput=false;
    }
    else{
        nums.push_back(current);
    }
}
cout<<' ';

isfirstoutput=true;
while(!nums.empty()){
    cout<<(isfirstoutput ? "" : " ")<<nums.back();
    isfirstoutput=false;
    nums.pop_back();
}

return 0;
}

发表于 2025-11-16 14:07:38 回复(0)
Python3
GB279824头像 GB279824 
def find_maxstack(n,stack):
    s = []
    output = []
    maxnumber = n
    for num in stack:
        s.append(num)
        # 栈不为空，且栈顶元素为最大值
        while s and s[-1] == maxnumber:
            output.append(s.pop()) # 出栈，并保存操作
            maxnumber -= 1 # 最大值减一
    # 栈中剩余元素直接输出
    while s:
        output.append(s.pop())
    return output


n = int(input().strip())
stack = list(map(int,input().strip().split(" ")))

print(" ".join(map(str,find_maxstack(n,stack))))

发表于 2025-06-11 00:18:19 回复(0)
C
Comeand头像 Comeand

这很贪心了



#include <stdio.h>
#define MAXN 1000005

int stack[MAXN];              //贪心思想；一旦有符合预期的直接带走，然后把预期减小
int p[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    int top = -1;
    int max_val = n;
    int i = 0;
    while (i < n || top >= 0) {
        if (i < n) {
            stack[++top] = p[i++];
            // 出栈所有等于当前max_val的元素
            while (top >= 0 && stack[top] == max_val) {
                printf("%d ", stack[top--]);
                max_val--;
            }
        } else {
            // 出栈剩余元素
            printf("%d ", stack[top--]);
        }
    }
    return 0;
}
发表于 2025-11-24 13:50:23 回复(0)
Solitude_sundae头像 Solitude_sundae
#include <bits/stdc++.h>
using namespace std;
int main() {
stack <int> a;
int findmax(int x[], int size, int m);
int n, max;
cin >> n;
int p[n + 1];
for (int i = 1; i <= n; i++)
cin >> p[i];
max = findmax(p, n, 1);
for (int k = 1; k <= n; k++) {
if (p[k] != max)
a.push(p[k]);
else {
cout << p[k] << " ";
p[k] = 0;
max = findmax(p, n, k);
}
}
while (!a.empty()) {
cout << a.top() << " ";
a.pop();
}
}
int findmax(int x[], int size, int m) {
int temp = x[m];
for (int i = m + 1; i <= size; i++) {
if (x[i] > temp)
temp = x[i];
}
return temp;
}
// 64 位输出请用 printf("%lld")
发表于 2025-11-05 20:38:14 回复(0)
牛客339037212号头像 牛客339037212号
a = int(input())
m  = []
n = []
s = list(map(int,input().strip().split()))
for j in range(len(s)):
    m.append(s[j])
    if s[j] == a:
        n.append(m.pop())
        a -= a
while m:
    n.append(m.pop())

print(*n)
发表于 2025-10-02 16:20:45 回复(0)
C
123456789201803221944171头像 123456789201803221944171

include <stdio.h>

include <stdlib.h>

typedef struct Stack {
int* base;
int top;
} Stack;
void initstack(Stack* p, int capacity) {
int* s = (int)malloc(sizeof(int) * capacity);
if (!s) exit(1);
p->base = s;
p->top = 0;
}
void push_stack (Stack p, int v) {
p->base[p->top++] = v;

}
void pop_stack(Stack* p) {
p->top--;
}
int top(Stack* p) {
return p->base[p->top - 1];
}

int main() {
int a = 0;
scanf("%d", &a);
int* P = (int*)malloc(sizeof(a) * a) ;
if (!P) exit(1);
for (int i = 0; i < a; i++) {
scanf("%d ", &P[i]);
}
Stack mystack;
int j = 0;
initstack(&mystack, a);
for (int i = 0; i < a; i++) {
while (j < a) {
push_stack(&mystack, P[j++]);
if (top(&mystack) == a - i) {
break;
}
}

    if (i < a) {
        printf("%d ", top(&mystack));
    } else {
        printf("%d\n", top(&mystack));
    }
    pop_stack(&mystack);
}
free(P);
free(mystack.base);
P = mystack.base = NULL;
return 0;

}

int* base;

int top;

} Stack;

void initstack(Stack* p, int capacity) {

int* s = (int*)malloc(sizeof(int) * capacity);

if (!s) exit(1);

p->base = s;

p->top = 0;

}

void push_stack (Stack* p, int v) {

p->base[p->top++] = v;

}

void pop_stack(Stack* p) {

p->top--;

}

int top(Stack* p) {

return p->base[p->top - 1];

}

int main() {

int a = 0;

scanf("%d", &a);

int* P = (int*)malloc(sizeof(a) * a) ;

if (!P) exit(1);

for (int i = 0; i a; i++) {

    scanf("%d ", &P[i]);

}

Stack mystack;

int j = 0;

initstack(&mystack, a);

for (int i = 0; i a; i++) {

    while (j a) {

        push_stack(&mystack, P[j++]);

        if (top(&mystack) == a - i) {

            break;

        }

    }

    if (i a) {

        printf("%d ", top(&mystack));

    } else {

        printf("%d\n", top(&mystack));

    }

    pop_stack(&mystack);

}

free(P);

free(mystack.base);

P = mystack.base = NULL;

return 0;

}

发表于 2025-08-14 11:01:48 回复(0)
badcola头像 badcola
只需要先逆序排列，然后每个元素入栈之前先检查其是否是当前最大值，如果是就出栈，最后把栈里的元素合并进输出序列即可。
from re import T
import sys

n = int(input())
P = list(map(int,input().split()))

class Stack:
    def __init__(self) -> None:
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
           

    def is_empty(self):
        return len(self.items) == 0

    def peek(self):  # 修正拼写
        if not self.is_empty():
            return self.items[-1]
        return None
   
    def size(self):
        return len(self.items)

stack = Stack()
out = []
j = 0
s = sorted(P,reverse=True)

for i in P:
    stack.push(i)
    if i == s[j] and j < len(s):
        out.append(i)
        j += 1
        stack.pop()

while not stack.is_empty():
    out.append(stack.pop())

print(' '.join(map(str, out)))
   

       
       
 

   
   


发表于 2025-07-31 19:49:20 回复(0)
Java
拒绝无效加班的柯基很想被叫靓仔头像 拒绝无效加班的柯基很想被叫靓仔
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            Deque<Integer> stack = new ArrayDeque<>();
            int[] list = new int[n];
            int max = 0;//定义一个max值来判断是否出栈
            for(int i = 0;i < list.length;i++){
                list[i] = in.nextInt();
                if(list[i] > max){max = list[i];}
            }
            int count = max;
            stack.push(list[0]);//先将第一个元素入栈防止循环中判断栈空报错
            for(int i = 1;i < list.length;i++){
                stack.push(list[i]);
                if(list[i] == count){System.out.print(stack.pop() + " ");count--;}
                //如果入栈的元素==max则出栈
            }
            while(!stack.isEmpty()){
                //循环结束若栈空则无法输出完全严格排序，将栈中剩下的元素依次输出
                System.out.print(stack.pop() + " ");
            }
        }
    }
}
发表于 2025-07-14 09:50:15 回复(0)
起源s头像 起源s
import java.util.Scanner;
import java.util.Stack;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int max = n;
        Stack<Integer> stk = new Stack<>();
        for(int i=0;i<n;i++)
        {
            int num = in.nextInt();
            stk.push(num);
            while(!stk.isEmpty())
            {
                if(!stk.isEmpty()&&stk.peek()==max)
                {
                    int res = stk.pop();
                    System.out.print(res+" ");
                    max--;
                }
                else
                {
                    break;
                }    
            }
           
        }
        while(!stk.isEmpty())
        {
            System.out.print(stk.pop()+" ");
        }
    }
}
发表于 2025-07-08 19:45:02 回复(0)
提交观点

问题信息

上传者：牛客301599号
难度：
11条回答 4505浏览

热门推荐

通过挑战的用户

查看代码

相关试题

栈和排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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