LeetCode 1673. 找出最具竞争力的子序列
目录
题目描述
题意分析
从
nums里挑出长度恰好为k的子序列，要求它「最具竞争力」。题面对竞争力的定义是：两个等长序列比较时，在第一个不同的位置上数字更小的那个更具竞争力。这其实就是字典序最小。子序列意味着只能删不能换位，剩下元素的相对顺序必须保持原样。长度恰好是
k，不是至多也不是至少，等价于「从n个元素里删掉n - k个」。「字典序最小」这个目标有一个很强的性质：它是逐位贪心的。第一位取到的数字越小，整个序列就越优，无论后面几位如何——因为比较在第一个不同的位置就分出胜负了。所以决策可以从左往右逐位敲定，不存在「牺牲前面换后面」的权衡。
但逐位取最小要受一个约束：选完第
t位之后，右边必须还留有足够多的元素来填满剩下的k - t位。这条「够不够用」的约束是本题全部难点所在。数据规模是 $n \le 10^5$，
k不超过n。这个量级排除了 $O(nk)$ 的逐位扫描（$k$ 可达 $10^5$ 时退化为 $10^{10}$），要求单趟线性解法。边界包括：
k == n（只能原样返回）；数组严格递减（一个都不能删，因为删了就凑不够）；数组严格递增（只能保留前k个）；以及大量重复元素时相等的两个数不该互相替换。
解法：单调栈选最小字典序
核心思路
长度必须为
k，等价于恰好删除remove = n-k个元素。扫描数组时，用数组模拟答案栈。若当前值
value小于栈顶，且仍有删除额度，就删除栈顶。这个交换会让当前尚未确定的最靠前位置变小，字典序严格改善；删除次数和元素顺序都仍合法。只要条件持续成立就继续弹栈，因此可能一次替换多个较大的尾部元素。当栈顶不大于当前值时，保留更早的栈顶不会变差；当删除额度为 0 时，更不能再替换。若栈尚未达到
k就压入当前值；若栈已满，当前值只能被删除，并消耗一次额度。不变量是：已扫描元素要么在栈中，要么已经计入删除额度，且栈是这些元素在当前删除约束下能得到的最小字典序前缀。每次弹出较大栈顶都是必然改进；不能弹时保留现有前缀是最优的。扫描结束后共处理
n个元素并恰好删除n-k个，所以栈长度恰好为k。
解题步骤
- 初始化长度为
k的栈数组、size = 0、remove = n-k。- 对每个值，只要栈非空、栈顶更大且
remove > 0，就弹栈并减少删除额度。- 若栈未满则压入当前值；否则删除当前值并减少额度。
- 扫描结束后直接返回栈数组。
[3,5,2,6], k = 2的删除额度为 2。遇到 2 时依次弹出 5、3，用完额度后压入 2，最后压入 6，得到[2,6]。
k = n时删除额度为 0，任何元素都不能弹出，结果保持原数组。对于[1,1,2], k = 2，相等的 1 不应互相替换，最终删除末尾 2，得到[1,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)$。
关键点总结
- 长度
k转换成删除额度n-k，可直接控制单调栈的弹出次数。- 后来的更小值可以替换栈顶，使第一个不同位置更小。
- 弹栈条件必须使用严格大于；相等时替换不改善字典序。
- 删除额度耗尽后不能再弹，即使后续值更小。
- 栈已满而当前值无法改善前缀时，删除当前值。
易错点总结
- 弹出相等元素会浪费删除额度；
[1,1,2], k=2应保留两个 1。- 忘记检查
remove > 0，在k = n时会弹出元素并导致结果不足k个。- 只用
if弹一次不足以移除连续较大栈顶；[3,5,2,6], k=2需要连续弹两次。- 栈满后覆盖栈顶会改变已确定前缀；无法改善时应删除当前值。
- 先排序再取最小值会破坏子序列的原始相对顺序。
- 把
k当删除数会返回错误长度；删除额度应是n-k。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 402. 移掉 K 位数字 | 中等 | 与本题同构，但给的是删除个数，守卫改成剩余删除额度，还要处理前导零 |
| 316. 去除重复字母 | 中等 | 额外要求每个字母恰好出现一次，弹栈前必须确认该字母后面还会再出现 |
| 1081. 不同字符的最小子序列 | 中等 | 与 316 同题，可直接套用带「后续出现次数」守卫的模板 |
| 321. 拼接最大数 | 困难 | 把本题当子过程调用两次再枚举分配方案合并，考点升级为多序列组合 |
| 738. 单调递增的数字 | 中等 | 同样是逐位贪心构造，但只能减小某一位并把后面全置 9，无需栈 |
| 739. 每日温度 | 中等 | 单调栈的另一大用途：求下一个更大元素，弹栈时结算答案而非丢弃 |
| 84. 柱状图中最大的矩形 | 困难 | 栈里存下标而非值，弹栈时用左右边界计算面积，展示同一结构的不同结算方式 |
| 946. 验证栈序列 | 中等 | 栈的行为由输入序列指定而非贪心决定，考点是模拟而非最优化 |