首页 > 试题广场 >

栈和排序

[编程题]栈和排序

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

$\hspace{15pt}$ 给定一个从 $1$ 到 $n$ 的排列 $P$ ，以及一个空栈。你按顺序将排列中的元素依次入栈，可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。

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

输入描述:

在一行中输入一个整数  。 
第二行输入  个整数，表示排列  中的元素，用空格分隔。保证给出的是一个从  到  的排列。

输出描述:

输出一行，包含若干整数，表示最终的出栈序列，用空格分隔，结尾不输出多余空格。

示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

入栈顺序和操作示例如下： 
2 入栈； 
1 入栈； 
5 入栈； 
5 出栈； 
3 入栈； 
4 入栈； 
4 出栈； 
3 出栈； 
1 出栈； 
2 出栈。

备注:

算法知识视频讲解

查看答案及解析

Python3

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/C++

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)