找出最具竞争力的子序列

难度: Medium

给你一个整数数组 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

Submission

运行时间: 90 ms

内存: 28.2 MB

from typing import List

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = []
        remain = len(nums) - k
        
        for num in nums:
            while stack and stack[-1] > num and remain > 0:
                stack.pop()
                remain -= 1
            stack.append(num)
        
        return stack[:k]

Explain

题解采用单调栈的思路来解决问题。具体方法是遍历输入数组 nums，使用栈（stack）存储潜在的最具竞争力的子序列。对于每个元素 num，首先检查栈顶元素是否大于当前元素 num，并且检查是否还有足够的剩余元素（remain）可以从栈中移除。如果条件满足，则将栈顶元素弹出，这样做是为了保持栈中的元素尽可能小以形成最具竞争力的子序列。此外，每弹出一个元素，remain就减少1，表示可以丢弃的元素数减少。最后，将当前元素 num 压入栈中。遍历结束后，栈中可能的元素数量大于 k，因此只取前 k 个元素作为结果。这种方法确保了在满足长度为 k 的条件下，得到的子序列是最小的。

时间复杂度: O(n)

空间复杂度: O(n)

from typing import List

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stack = [] # 初始化栈，用于存储子序列
        remain = len(nums) - k # 可以移除的元素总数
        
        for num in nums: # 遍历数组
            while stack and stack[-1] > num and remain > 0: # 栈非空，且栈顶元素大于当前元素，且还可以移除元素
                stack.pop() # 移除栈顶元素，使子序列更小
                remain -= 1 # 更新可以移除的元素数量
            stack.append(num) # 将当前元素加入栈
        
        return stack[:k] # 返回栈中前k个元素

Explore

单调栈被用于这种问题是因为它能有效地维护一个递增（或递减）的元素序列，并且可以在O(1)时间复杂度内对栈顶元素进行增加或删除操作。这一点对于当前问题尤为重要，因为我们需要依据当前元素与栈顶元素的比较来决定是否需要移除栈顶元素以保证子序列的竞争力。使用堆或优先队列虽然可以快速找到最小或最大元素，但在删除非顶部元素时通常需要O(log n)的时间复杂度，这会增加整体的时间成本。此外，堆和优先队列不支持像栈一样轻松地移除序列中间的元素，这是解决此问题时必需的。

题解中的单调栈策略确保了在每一步都尽可能地保持子序列元素的最小性。当栈顶元素大于当前元素时，移除栈顶元素可以使得当前的子序列更小，从而更具竞争力。这种策略假设后续元素能填补被移除元素的位置而不损害总体大小，这是基于输入数组的完整遍历来保证的。然而，确实存在一些极端情况（尽管非常罕见），如果后续没有足够小的元素来替代被移除的元素，可能会导致子序列不是最优的。但在大多数情况下，这种策略是有效且能够获得最具竞争力的子序列的。

在题解中，remain变量表示可以从栈中移除的元素数量，它是由总元素数减去所需子序列长度k得到的。每次从栈中弹出一个元素时，remain减1。这个检查确保只有当还有足够的元素可以被移除时才进行弹出操作。这样做的目的是为了保证即使进行了栈顶元素的移除，数组中仍有足够多的剩余元素可以用来填补栈，确保最终栈的长度至少为k。如果remain为0，则意味着已经没有多余的元素可以移除，此时停止弹出操作，以确保栈的长度。