https://leetcode.cn/problems/find-the-most-competitive-subsequence/
一、题目解析
给定整数数组 nums 和正整数 k，返回长度为 k 的最具竞争力子序列。
"最具竞争力"的定义是：在两个序列的第一个不同位置上，元素更小的那个序列更有竞争力。说白了就是字典序最小。
以 nums = [3,5,2,6], k = 2 为例，长度为 2 的子序列有 [3,5]、[3,2]、[3,6]、[5,2]、[5,6]、[2,6]。逐对比较第一个不同位置，[2,6] 以 2 开头，完胜其他所有候选——它就是答案。
所以问题转化为：从原数组中按顺序选 k 个元素，使得结果序列字典序最小。
二、单调栈模板
如果只是找字典序最小的子序列且没有长度限制，用一个单调递增栈扫一遍就够了——遇到比栈顶小的元素就把栈顶弹掉。单调递增栈的基本模板：
Deque<Integer> stack = new ArrayDeque<>();for (int i = 0; i < n; i++) { while (!stack.isEmpty() && nums[stack.peekLast()] > nums[i]) { stack.pollLast(); // 弹出所有比当前元素大的栈顶 } stack.addLast(i);}走完这个循环，栈里就是一个递增序列，也是字典序最小的子序列。问题在于，本题要求子序列长度必须恰好为 k，弹太多了长度不够。
三、解题思路
3.1 弹的条件
单调栈弹出是为了"用更小的元素替换更大的元素"，但每次弹出都会减少最终子序列的长度。所以必须在弹出条件上加一个约束：弹出之后，剩余的备选元素还够凑满 k 个。
约束条件写出来就是：
stack.size() + nums.length - i > k其中 stack.size() 是弹出前栈的大小（因为 peekLast() 还在栈里），nums.length - i 包括当前位置 i 以及它之后所有元素。两者的和 > k，说明即使弹出栈顶，后面还有足够多的元素补位。
3.2 完整推演
以 nums = [3,5,2,6], k = 2 推一遍：
i=0, nums[0]=3：栈空，入栈 [0]
i=1, nums[1]=5：3<5，递增，入栈 [0, 1]。此时栈状态：[3, 5]
i=2, nums[2]=2：
· 5>2，检查约束：stack.size()=2，剩余=4-2=2，2+2=4>2 ✓，弹出 1(5)
· 3>2，检查约束：stack.size()=1，剩余=4-2=2，1+2=3>2 ✓，弹出 0(3)
· 栈空，入栈 [2]。栈状态：[2]
i=3, nums[3]=6：2<6，递增，入栈 [2, 3]。栈状态：[2, 6]
遍历结束，栈里是 [2, 6]，正好 k=2，就是答案。
3.3 为什么最后还要截断
遍历完成后栈里可能超过 k 个元素——因为当约束条件阻止弹出时，"不够弹"的元素会留在栈里。但此时栈的前 k 个一定是字典序最小的，因为所有可以弹的都已经在遍历中弹掉了。所以最后从栈头取前 k 个即可。
四、代码实现
class Solution { public int[] mostCompetitive(int[] nums, int k) { // 单调递增栈，存索引 ArrayDeque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < nums.length; i++) { // 弹出条件：栈非空、当前元素更小、弹出后剩余元素还够凑满k while (!stack.isEmpty() && nums[stack.peekLast()] > nums[i] && (stack.size() + nums.length - i) > k) { stack.pollLast(); } stack.addLast(i); } // 栈可能多于k个，取前k个即可 int[] ans = new int[k]; int idx = 0; while (idx < k && !stack.isEmpty()) { ans[idx++] = nums[stack.removeFirst()]; } return ans; }}时间复杂度 O(n)，每个元素入栈一次、出栈一次。空间复杂度 O(k)，栈中最多存 k 个索引。
本文由 AgentPlanFlow 生成