LeetCode 1673. 找出最具竞争力的子序列

约 4 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 栈 贪心 单调栈

题目描述

✅ 1673. 找出最具竞争力的子序列

image-20260929090824600

题意分析

从数组中选择恰好 k 个元素，保持原来的相对顺序，使结果字典序最小。比较两个等长序列时，只看第一个不同的位置，那里更小的序列更优，因此应优先改善靠前的元素。

解法：单调栈选最小字典序

核心思路

[!blue]
保留 k 个元素等价于删除 n-k 个元素。 用栈保存当前候选前缀，remove 记录剩余删除额度。遇到当前值 value 时，若栈顶更大且还有额度，就删除栈顶，让这个更小的值有机会出现在更靠前的位置。

弹出较大栈顶后，两种选择之前的前缀相同，而新选择在第一个不同位置更小，字典序就已经改善，不会被后续元素推翻。因此应连续弹出所有可以删除的较大栈顶。相等时没有改善，保留较早的元素还能给后面留下更多选择，不应消耗额度。

弹栈结束后，栈未满就加入当前值；栈已满则跳过当前值，这也算一次删除。额度为 0 时，剩余元素必须按原顺序保留，此后栈不一定单调，不能为了维持单调继续弹出。

长度不会不足：已处理元素始终等于“栈内元素数 + 已删除数”，删除总数不超过 n-k，栈长度又不超过 k，处理完 n 项时只能恰好留下 k 项。栈已满但仍有新元素时也必然还有删除额度，否则 k 个保留项和 n-k 个删除项已经处理完全部数组。

解题步骤

  1. 初始化容量为 k 的答案栈，以及 remove=n-k。
  2. 从左到右读取 value，只要栈非空、栈顶更大且 remove>0，就弹栈并减少一次额度。
  3. 栈长度不足 k 时压入 value；否则跳过它并减少一次额度。
  4. 遍历结束，返回栈中的 k 个元素。

k=n 时没有删除额度，结果就是原数组；k=1 时保留最小元素。数组已经递增或元素全相等时，不发生弹栈，后面超出长度的元素通过跳过删除，仍能满足长度要求。

代码实现

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int[] stack = new int[k];
        int size = 0;
        int remove = nums.length - k;

        for (int value : nums) {
            // 仍有删除额度时，用后来的更小值替换较大栈顶。
            while (size > 0 && remove > 0 && stack[size - 1] > value) {
                size--;
                remove--;
            }

            if (size < k) {
                stack[size++] = value;
            } else {
                // 栈已满，跳过当前元素也算一次删除。
                remove--;
            }
        }

        return stack;
    }
}

func mostCompetitive(nums []int, k int) []int {
    stack := make([]int, 0, k)
    remove := len(nums) - k

    for _, value := range nums {
        // 仍有删除额度时，用后来的更小值替换较大栈顶。
        for len(stack) > 0 && remove > 0 && stack[len(stack)-1] > value {
            stack = stack[:len(stack)-1]
            remove--
        }
        if len(stack) < k {
            stack = append(stack, value)
        } else {
            // 栈已满，跳过当前元素也算一次删除。
            remove--
        }
    }
    return stack
}

复杂度分析

  • 时间复杂度：$O(n)$，每个元素至多入栈和出栈各一次。
  • 空间复杂度：$O(k)$，栈就是输出；其他辅助空间 $O(1)$。

关键点总结

[!green]

  • 字典序优先改善最靠前的位置。
  • 删除额度同时约束替换和跳过。
  • 相等元素保留较早者，不浪费可用额度。

易错点总结

[!yellow]

  • 弹栈不检查额度：最后可能不足 k 个元素。
  • 只弹出一次：可能留下连续多个更大的栈顶。
  • 相等也弹出：没有改善字典序，却消耗删除机会。
  • 先排序再取 k 个：破坏子序列顺序。

相似题目

题目 难度 关联与区别
402. 移掉 K 位数字 中等 同样在还能补足目标长度时弹出较大前缀，本题返回固定长度数组，不能删掉结果中的前导0。
321. 拼接最大数 困难 同样选择固定长度最优子序列，原题取最大并合并两来源，本题只取单来源字典序最小。
316. 去除重复字母 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题保留固定长度的最具竞争力子序列，该题每种字符保留一次并追踪剩余次数。
1081. 不同字符的最小子序列 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题保留固定长度的最具竞争力子序列，该题选择每种不同字符一次的最小字典序子序列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/25723881
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！