C语言学习笔记20260705-基于栈的排列重排——求字典序最大的合法出栈序列

1. 题目概述

给定一个从 1到 n 的排列 P，以及一个空栈。我们需要按顺序将排列中的元素依次入栈，并可以在任意时刻选择将栈顶元素出栈并将其加入输出序列（入栈顺序不可改变）。

理想情况下，我们希望得到一个严格从大到小排序的输出序列。但受栈操作限制，可能无法完全实现。当无法完全排序时，请输出字典序最大的合法出栈序列。

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

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

---

2. 核心难点与贪心策略

入栈顺序不可改变，但出栈时机可以自由决定。本题的核心难点在于：什么时候该弹出栈顶元素？

要想让输出序列的字典序最大，贪心的思想是“尽可能让大的数字靠前”。如果当前栈顶元素为 x，而后续未入栈的元素中存在比 x 更大的数字 y，那么 y 入栈后出栈，得到的字典序一定比现在更大就把 x弹出来。

因此，贪心策略的核心判断条件是：
只有当栈顶元素大于或等于后续所有未入栈元素的最大值时，才将其弹出。 如果后续还有更大的数等待入栈，当前栈顶就必须暂时留在栈中，以免阻塞更大元素的输出。

---

3. 算法思路：后缀最大值 + 模拟栈

为了在 O(1)时间内判断“后续是否还有更大的数”，我们需要提前预处理出后缀最大值。整个算法分为三步：

第一步：预处理后缀最大值

定义数组 suf_max[i]，表示从位置 i 到数组末尾中，所有元素的最大值。通过从后往前遍历一次即可求出：
suf_max[i] = max(P[i], suf_max[i+1])
这样，当我们处理到第 i个元素时，suf_max[i+1] 就代表了“后面所有未入栈元素的最大值”。

第二步：逐个入栈，贪心弹出

遍历排列 P，将元素依次压入栈中。每次压入后，检查栈顶元素与后缀最大值的关系：

• 若 栈顶元素 >= suf_max[下一个未入栈位置]，说明后面没有比它更大的数了，安全弹出并输出。
• 循环检查，直到栈为空或栈顶元素小于后缀最大值。

第三步：清空栈中剩余元素

当所有元素都入栈并处理完毕后，栈中剩余的元素只能按照“先进后出”的顺序依次弹出，追加到输出序列的末尾。

---

4. 完整代码实现

以下是基于 C 语言的完整实现，使用 malloc 动态分配内存以应对 n高达 10^6 的数据规模，避免函数栈溢出：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n;
    scanf("%d", &n);

    // 堆分配数组，不占用函数栈，无全局变量
    int* P = (int*)malloc(sizeof(int) * (n + 2));
    int* suf_max = (int*)malloc(sizeof(int) * (n + 2));
    int* stk = (int*)malloc(sizeof(int) * (n + 2));
    int top = 0;

    // 读取入栈序列
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &P[i]);
    }

    // 倒序预处理后缀最大值
    suf_max[n] = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        suf_max[i] = (P[i] > suf_max[i + 1]) ? P[i] : suf_max[i + 1];
    }

    int ptr = 0;
    for (int i = 0; i < n; i++)
    {
        stk[top++] = P[i]; // 当前元素先入栈
        ptr = i + 1;       // ptr指向下一个即将入栈的元素位置
        
        // 核心贪心判断：栈顶大于等于后续所有未入栈元素最大值，立即弹出
        while (top > 0 && stk[top - 1] >= suf_max[ptr])
        {
            // 处理输出格式，避免结尾多余空格
            if (ptr == n && top == 1)
                printf("%d", stk[--top]);
            else
                printf("%d ", stk[--top]);
        }
    }

    // 弹出栈内剩余元素
    while (top > 0)
    {
        if (top == 1)
            printf("%d", stk[--top]);
        else
            printf("%d ", stk[--top]);
    }

    // 释放堆内存，避免内存泄漏
    free(P);
    free(suf_max);
    free(stk);
    return 0;
}

---

5. 复杂度分析

环节	复杂度	说明
时间复杂度	O(n)	预处理后缀最大值遍历一次 O(n)；每个元素最多入栈一次、出栈一次，模拟过程也是 O(n)。
空间复杂度	O(n)	需要三个大小为 n 的数组来存储排列、后缀最大值和模拟栈。

---

6. 关键设计总结

• 后缀最大值是灵魂：它将“未来的信息”提前计算好，把原本需要暴力搜索的 O(n^2) 复杂度优化到了 O(n)，使得贪心决策可以在常数时间内完成。
• 贪心策略的本质：栈顶元素只有在“后面不可能出现比它更大的数”时才弹出。这既保证了不会阻塞更大元素的输出，又让较大的数尽可能早地出现在输出序列中，从而最大化字典序。
• 工程实践细节：代码中使用 malloc 动态分配内存并在使用后 free，避免了在 n较大时发生栈溢出（Stack Overflow）和内存泄漏，是处理大规模数据时的良好习惯。