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

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>intmain(){intn;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));inttop=0;// 读取入栈序列for(inti=0;i<n;i++){scanf("%d",&P[i]);}// 倒序预处理后缀最大值suf_max[n]=0;for(inti=n-1;i>=0;i--){suf_max[i]=(P[i]>suf_max[i+1])?P[i]:suf_max[i+1];}intptr=0;for(inti=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]);elseprintf("%d ",stk[--top]);}}// 弹出栈内剩余元素while(top>0){if(top==1)printf("%d",stk[--top]);elseprintf("%d ",stk[--top]);}// 释放堆内存，避免内存泄漏free(P);free(suf_max);free(stk);return0;}

5. 复杂度分析

6. 关键设计总结

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