发表于 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

• LC 题目链接