leetcode 1673 - Find the Most Competitive Subsequence

https://leetcode.com/problems/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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
stack<int> stk;

int size = nums.size();

for (int i = 0; i < size; i++) {
while (!stk.empty() && nums[i] < stk.top() && stk.size() - 1 + size - i >= k)
stk.pop();

if (stk.size() < k)
stk.push(nums[i]);
}

vector<int> result;
while (!stk.empty()) {
result.push_back(stk.top());
stk.pop();
}

reverse(result.begin(), result.end());

return result;
}
};