LeetCode 补充题 133. 字典序最大的出栈序列
题目描述
牛客原题： ✅ 补充题 133. 字典序最大的出栈序列
给你一个由
1到n组成的排列nums。所有元素必须按给定顺序进入同一个栈，但你可以在任意合法时刻弹出栈顶元素。请返回所有合法出栈序列中字典序最大的一个。整个过程只允许入栈和出栈两种操作。
示例 1：
输入：
nums = [2,1,3]
输出：[3,1,2]
解释： 先依次入栈2、1、3，再依次出栈。输出3后，1在2上方，因此不能得到[3,2,1]。
示例 2：
输入：
nums = [3,1,2]
输出：[3,2,1]
解释： 3 入栈后立即出栈；再将 1、2 入栈，依次弹出 2、1。
提示：
1 <= n <= 5 * 10^4- 排列中的值都满足
1 <= val <= n
题意分析
字典序由第一个不同的输出位置决定，所以应让当前能合法输出的下一项尽量大。可选择的是立即弹出栈顶，或继续按输入顺序压栈；栈内更深元素被栈顶挡住，不能直接取出。
解法：后缀最大值决定栈顶何时输出
核心思路
[!blue]
suffix[i]表示从i开始的剩余输入最大值。每次压入nums[i]后，比较栈顶与suffix[i+1]：若未来存在更大的数，可以一直压入到它出现，使下一项更大，因此应等待。若栈顶比未来所有数都大，继续压入只会让较小元素挡在它上方，不能改善当前输出；立即弹出是最优选择。弹出后对新栈顶重复判断，逐项固定字典序最优的前缀。
输入是
1～n的排列，值均为正且不重复，因此用 0 表示空后缀最大值。最后一次压栈后所有剩余栈顶都大于 0，都会被弹出，不会遗留元素。
解题步骤
- 逆序求尚未入栈元素的后缀最大值。
- 按输入次序压栈。
- 栈顶大于剩余输入的最大值时持续出栈，得到字典序最大结果。
代码实现
class Solution {
public int[] stackOrder(int[] nums) {
int n = nums.length;
int[] suffix = new int[n + 1];
int[] stack = new int[n];
int[] result = new int[n];
for (int i = n - 1; i >= 0; i--) {
suffix[i] = Math.max(nums[i], suffix[i + 1]);
}
int size = 0;
int write = 0;
for (int i = 0; i < n; i++) {
stack[size++] = nums[i];
while (size > 0 && stack[size - 1] > suffix[i + 1]) {
result[write++] = stack[--size];
}
}
return result;
}
}
func stackOrder(nums []int) []int {
n := len(nums)
suffix := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
suffix[i] = max(nums[i], suffix[i+1])
}
stack := make([]int, 0, n)
result := make([]int, 0, n)
for i, x := range nums {
stack = append(stack, x)
for len(stack) > 0 && stack[len(stack)-1] > suffix[i+1] {
result = append(result, stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
每一位都尽量先输出仍可取得的最大值，且不打乱输入次序；栈顶不满足条件时不能跳过它输出更深的值。
易错点总结
[!yellow]
输入是1…n的排列，末尾最大值哨兵可以取0；不能直接排序结果，也不能引入第二个辅助栈重排。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 946. 验证栈序列 | 中等 | 原题给定出栈序列验证合法性，本题在合法操作中主动选择字典序最大的结果。 |
| 2434. 使用机器人打印字典序最小的字符串 | 中等 | 同样依据尚未入栈的极值决定何时弹出；原题求字典序最小且允许重复字符，本题求最大且输入为排列。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！