Given an integer array nums and a positive integer k, return the most competitive subsequence of nums of size k.

An array’s subsequence is a resulting sequence obtained by erasing some (possibly zero) elements from the array.

We define that a subsequence a is more competitive than a subsequence b (of the same length) if in the first position where a and b differ, subsequence a has a number less than the corresponding number in b. For example, [1,3,4] is more competitive than [1,3,5] because the first position they differ is at the final number, and 4 is less than 5.

Example 1:

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

Example 2:

Input: nums = [2,4,3,3,5,4,9,6], k = 4
Output: [2,3,3,4]

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
1 <= k <= nums.length

Solution

Time complexity : O(n)
Space complexity : O(k)

class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> ans;
        for (int i=0; i<n; ++i) {
            while (!ans.empty() && nums[i]<ans.back() && k<=(ans.size()-1)+(n-i))
                ans.pop_back();
            if (ans.size() < k) ans.push_back(nums[i]);
        }
        return ans;
    }
};

將答案用一個 stack 裝起來，若目前第 i 個 < stack 最後一個，就可以 pop stack，用較小的數字塞入。

但在做這件事之前，先確認往後是否有足夠的數字可以塞入 stack 使其滿 k 個。
stack pop 後的 size 為：stack.size() - 1
往後剩餘的元素量為：nums.size() - i
因此必須確保 k <= (stack.size()-1) + (nums.size()-i)

然後若 stack 不滿 k 個的話，一律塞入 stack。