JZX轻语：简
LeetCode 1673 - 找出最具竞争力的子序列
发表于2024年05月24日
由题目得知，如果子序列前面的值越小，则越具竞争力，即尽可能找到较小的值放在前面。本质就是找到一个子数组，其中第一个元素为nums[0..n-k]中的最小值，第二个元素为nums[第一个元素位置+1..min(n-1, n-k+1)]中的最小值，第三个元素及后面亦然(注意区间的右侧，我们不能直接取最小值，否则即便追加后面所有的元素都无法构成长度为k的结果)。朴素的想法可以使用一个堆，先维护nums[0..n-k]中的元素，然后开始循环，取出栈顶(当前最小值)，如果栈顶的位置位于结果数组最后一个元素的右边，则加入到结果数组中，并将原数组未加入到堆中的最左边元素放进堆里面，直至结果数组填充完毕。
更高效的方式是使用单调栈(并不一定单调，只是处理的方式同单调栈，尽可能将较小的元素放在最前面)来充当当前循环的最优解：如果当前元素小于栈顶，且栈顶弹出后不影响结果的长度等于k(所谓的影响即，弹出后再加入该元素，并将该元素后所有元素添加上去，长度都小于k)。
class Solution:
def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
stack = [0] * k
stack_actual_size = 0
for i, num in enumerate(nums):
# 需要保证能构成结果: 如果弹过多的话, 全拼接后面的数组元素也够不成完整结果的话, 就不要再弹了
while stack_actual_size > 0 and stack[stack_actual_size - 1] > num and stack_actual_size - 1 + (len(nums) - i) >= k:
stack_actual_size -= 1
if stack_actual_size < k:
stack[stack_actual_size] = num
stack_actual_size += 1
return stack