https://leetcode.com/problems/find-the-most-competitive-subsequence/

题解

参考：
https://leetcode.com/problems/find-the-most-competitive-subsequence/discuss/952786/JavaC%2B%2BPython-One-Pass-Stack-Solution

class Solution:
    def mostCompetitive(self, nums: List[int], k: int) -> List[int]:

        """
        Monotonic increasing stack

        if current element smaller than last element in stack
        replace it with current

        need to make sure we still have enough before we do so
        """

        stack = []

        for i, num in enumerate(nums):
            while stack and stack[-1] > num and len(stack) - 1 + len(nums) - i >= k:
                stack.pop()
            if len(stack) < k:
                stack.append(num)

        return stack

反思

monotonic stack 的技巧之前没有见过。题还是刷得少。

这个应该也算是贪心解法？局部的最优解最后能够成为全局最优。

一开始用了 n^2 的办法，显然不行。

后来就开始想 nlogn 或者 nlogk，能不能用二分，找到一个分割点？但是无法确定判断左右指针移动的条件。

因为一直没有 O(n) 的线索。缺少直觉。

本题可以提取关键词：monotonic stack