LeetCode
comments powered by Disqus
Editorial: LeetCode 1673 Find the Most Competitive Subsequence
https://leetcode.com/problems/find-the-most-competitive-subsequence/ from Google
Thinking process:
Go through the example first.
We can pop 3 and 5 because
- 2x is always more competitive than 3x
- we know there’s enough element after 2
Another example.
Here is the code.
1class Solution {
2public:
3 vector<int> mostCompetitive(vector<int>& nums, int k) {
4 int N = nums.size();
5 vector<int> ans;
6 for (int i=0; i<N; i++) {
7 while (ans.size() > 0 and ans.back() > nums[i] and (ans.size() + N - i) >= (k+1)) {
8 ans.pop_back();
9 }
10 if (ans.size() < k) ans.push_back(nums[i]);
11 }
12 return ans;
13 }
14};