What is the key strategy to solve Find the Most Competitive Subsequence efficiently?

The key strategy is using a monotonic stack to maintain candidate elements while ensuring the subsequence remains lexicographically minimal and of size k.

Can we solve this problem without a stack?

A stack simplifies the logic and ensures O(n) time. Without it, you would need complex tracking of indices and elements, potentially increasing time complexity.

How do we handle ties when elements are equal in the subsequence?

Equal elements are treated as competitive in order; the first encountered element is kept, and popping only occurs when a strictly smaller number is found.

What if k equals the array length?

If k equals nums.length, the entire array is already the only subsequence of length k and is returned directly.

Does the solution pattern relate to other LeetCode problems?

Yes, the stack-based state management pattern appears in other greedy subsequence and monotonic stack problems, useful for lexicographical order optimizations.

#1673

Medium

auto_awesome栈·状态

LeetCode 题解工作台

找出最具竞争力的子序列

给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具竞争力的 nums 子序列。数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b （…

数组栈贪心单调栈

题目描述

给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。

数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。

在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。

示例 1：

输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最具竞争力。

示例 2：

输入：nums = [2,4,3,3,5,4,9,6], k = 4
输出：[2,3,3,4]

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
1 <= k <= nums.length

lightbulb

解题思路

方法一：栈

我们从左到右遍历数组 nums，维护一个栈 stk，遍历过程中，如果当前元素 nums[i] 小于栈顶元素，且栈中元素个数加上 $n-i$ 大于 $k$ ，则将栈顶元素出栈，直到不满足上述条件为止。此时如果栈中元素个数小于 $k$ ，则将当前元素入栈。

遍历结束后，栈中元素即为所求。

时间复杂度 $O(n)$ ，空间复杂度 $O(k)$ 。其中 $n$ 为数组 nums 的长度。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stk = []
        n = len(nums)
        for i, v in enumerate(nums):
            while stk and stk[-1] > v and len(stk) + n - i > k:
                stk.pop()
            if len(stk) < k:
                stk.append(v)
        return stk

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is pushed and popped at most once in the monotonic stack. Space complexity is O(k) since the stack only holds the subsequence of size k.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect recognition that a stack can maintain current candidates for lexicographical order.
question_mark
Probe whether the candidate removal logic respects remaining elements to reach size k.
question_mark
Check understanding of why left-side elements have higher priority than later ones.

warning

常见陷阱

外企场景

error
Not accounting for enough remaining elements when popping from the stack, causing subsequence length < k.
error
Confusing subsequence with subarray, leading to incorrect indexing.
error
Attempting a brute-force enumeration of all subsequences, which is infeasible for large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the most competitive subsequence under additional constraints like minimum sum or maximum product.
arrow_right_alt
Compute the lexicographically largest subsequence instead of smallest.
arrow_right_alt
Apply the monotonic stack approach to a circular array where wrapping is allowed.

help

常见问题

外企场景

继续练习

#1526 形成目标数组的子数组最少增加次数 #1996 游戏中弱角色的数量 #1130 叶值的最小代价生成树