1673. Find the Most Competitive Subsequence

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.

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