题解 | #栈和排序#

栈和排序

https://www.nowcoder.com/practice/b10a7ac681e9429e89a6a510e5799647

题目链接

栈和排序

题目描述

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

你的目标是得到字典序最大的合法出栈序列。

输入描述:

第一行输入一个整数 N。
第二行输入 N 个整数，表示排列 p 中的元素。

输出描述:

输出一行，包含 N 个整数，表示最终的字典序最大的出栈序列。

示例输入:

5
2 1 5 3 4

输出:

5 4 3 1 2

解题思路

要获得字典序最大的输出序列，我们的核心思想是尽可能早地输出较大的数字。这是一个典型的贪心策略问题。

具体算法如下：

确定目标: 我们想要输出的数字顺序是 N, N-1, N-2, ..., 1。我们用一个变量 expected_num 来追踪当前期望输出的最大数字，初始值为 N。
模拟入栈: 我们遍历给定的输入序列 p，按顺序将每个元素 x 压入一个辅助栈 s 中。
贪心出栈: 每当一个新元素 x 入栈后，我们就检查栈顶元素。如果栈不为空，且栈顶元素恰好是我们当前期望的 expected_num，我们就应该立即将其出栈。因为这是我们能让 expected_num 最早出现的机会，任何延迟（即先压入其它元素）都可能导致它被其它较小的数覆盖，从而无法实现字典序最大化。
- 我们将栈顶元素弹出，加入结果列表。
- 然后，我们将 expected_num 减 1，表示我们接下来要寻找下一个最大的数。
- 这个出栈的检查需要循环进行，直到栈为空或者栈顶元素不再是我们期望的那个数为止。
处理剩余元素: 当输入序列 p 中的所有元素都处理完毕后，栈中可能还剩下一些元素。此时我们别无选择，只能按照 LIFO (后进先出) 的顺序将它们全部弹出，并依次加入结果列表。
输出结果: 最后，将结果列表中的元素打印出来即可。

通过这个贪心策略，我们确保了在每个决策点都做出了能让当前输出序列尽可能大的选择，从而最终得到全局的字典序最大序列。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <stack>
#include <numeric>

using namespace std;

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

    stack<int> s;
    vector<int> result;
    int expected_num = n;

    for (int x : p) {
        s.push(x);
        while (!s.empty() && s.top() == expected_num) {
            result.push_back(s.top());
            s.pop();
            expected_num--;
        }
    }

    while (!s.empty()) {
        result.push_back(s.top());
        s.pop();
    }

    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << (i == result.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }

        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();
        int expectedNum = n;

        for (int x : p) {
            stack.push(x);
            while (!stack.isEmpty() && stack.peek() == expectedNum) {
                result.add(stack.pop());
                expectedNum--;
            }
        }

        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }

        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + (i == result.size() - 1 ? "" : " "));
        }
        System.out.println();
    }
}

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

stack = []
result = []
expected_num = n

for x in p:
    stack.append(x)
    while stack and stack[-1] == expected_num:
        result.append(stack.pop())
        expected_num -= 1

while stack:
    result.append(stack.pop())

print(*result)