1673. Find the Most Competitive Subsequence (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def mostCompetitive(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # mono stack
        stack = []
        for i, num in enumerate(nums):
            while stack and num < stack[-1]:
                if len(nums) - i + len(stack) == k:
                    return stack + nums[i:]
                stack.pop()
            if len(stack) < k:
                stack.append(num)
        return stack
    
        # max heap
        heap = []
        for i, num in enumerate(nums):
            while heap and num < -heap[0][0]:
                if len(nums) - i + len(heap) <= k:
                    break
                _, j = heapq.heappop(heap)
                nums[j] = -1
            if len(heap) < k:
                heapq.heappush(heap, (-num, i))
            else:
                nums[i] = -1
        return [x for x in nums if x >= 0]