1673. 找出最具竞争力的子序列（Rating 1802）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1673. 找出最具竞争力的子序列

Rating 1802

思路

思路1（个人思路）：有序容器

最具竞争力的含义就是：子序列需要字典序越小越好，即越靠前的数越小越好。

因为子序列长度固定为k，所以不能无脑取序列最小的数，取数时需要保证

取一个尽量小的数，且这个数后面至少还有k-1个数可以取

因此，考虑以下步骤

1. 取第一个数的时候，考虑在末尾k-1个数之前，取其中最小的数。
2. 取第二个数的时候，从以上取的第一个数的下标开始，到末尾k-2个数之前，取其中最小的数。
3. 以此类推

根据题目数据规模，需要一个复杂度<= O(NlogN)的有序容器，动态维护一段区间内的最小值和其对应的下标，支持插入和删除

使用优先队列就可以完成以上功能。

另外，在python中，也可使用SortedContainers内有序容器维护；在c++中，也可以使用multiset有序容器维护。

思路2（参考题解）：单调栈

参考题解后，也可以使用单调栈完成以上思路。

核心思路：维护一个单调栈。遍历输入的所有数，循环判断：如果当前的数比栈顶的数小，且后面还有足够多的数使得子序列的长度可以满足k，那么就用当前的数替代栈顶的数。

代码

思路1（个人思路）：有序容器

heapq

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        ind_st, ind_ed = 0, n - k # 从0开始取，且后面需要至少留k-1个数
        q = [] # 优先队列
        for ind in range(ind_st, ind_ed + 1):
            heapq.heappush(q, (nums[ind], ind)) # 将数字，和数字对应的index入队（python默认小顶堆，堆顶元素最小）
        ret = [] # 记录答案
        while k: # 取k个子序列
            num, ind = heapq.heappop(q) # 取堆顶数字和index
            if ind < ind_st: # 我们需要在ind_st和ind_ed中间取数，如果堆顶的index小于当前ind_st，则继续
                continue
            ret.append(num) # 加入答案
            ind_st = ind # 更新ind_st，即刚取的数之前所有的数就不能取了
            k -= 1 # 更新k
            ind_ed += 1 # 更新ind_ed，可以选的数又可以多1个了
            if ind_ed < n: # 更新优先队列
                heapq.heappush(q, (nums[ind_ed], ind_ed))
        return ret

SortedContainers.SortedSet

from sortedcontainers import SortedSet # 使用SortedSet维护

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        stst = SortedSet() # SortedSet
        n = len(nums)
        for i in range(n - k + 1): # 从0开始取，且后面需要至少留k-1个数
            stst.add((nums[i], i)) # 维护数字和数字对应的index
        st = 0 # 从0开始取
        i = n - k + 1 # 后面需要至少留k-1个数
        ret = [] # 记录答案
        while len(ret) < k:
            num, idx = stst[0] # 取最小的数和其对应的index
            ret.append(num) # 加入答案
            stst.remove((num, idx)) # 从容器中移除刚加入答案的数和其对应的index
            for j in range(st, idx): # 这个数之前的数就都不能用了，也要全部一一删除
                stst.remove((nums[j], j))
            st = idx + 1 # 更新st，从刚才加入答案的数的后面一位开始
            if i < n: # 更新i，可以选的数又可以多1个了
                stst.add((nums[i], i))
                i += 1
        return ret

思路2（参考题解）：单调栈

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        ret = [] # 维护答案，也同时是单调栈
        for idx, num in enumerate(nums): # 遍历所有数
            # 只要栈非空，且当前数比栈顶元素小，且后面还有足够多的数支持最终答案可以是k个数，就弹出栈顶元素
            while ret and num < ret[-1] and len(ret) + len(nums) - idx > k: 
                ret.pop()
            if len(ret) < k: # 当前答案还不到k个，加入当前num
                ret.append(num)
        return ret