0%

LeetCode 1673. Find the Most Competitive Subsequence

Posted on In

题目

原题在此
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

解析

第一个数是从第0个到第size - k个中最小的那个.
第二个数是从上一个数的index开始到size - k - 1中最小的那个
如果已经不能再搜索,就只能按序填上所有元素

代码

golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func mostCompetitive(nums []int, k int) []int {
    res := make([]int, k)
    idx, size := 0, len(nums)
    for i := 0; i < size; i++ {
        for idx > 0 && nums[i] < res[idx - 1] && size - i - 1 >= k - idx {
            idx--
        }
        
        if idx < k {
            res[idx] = nums[i]
            idx++
        }
    }
    return res;
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> mostCompetitive(vector<int>& nums, int k) {
        vector<int> res(k);
        int c = 0, n = nums.size();
        for(int i = 0; i < n; i++) {
             while(c > 0 && res[c - 1] > nums[i] && n - i -1 >= k - c) c--;
             if(c < k) res[c++] = nums[i];
        }
        return res;
    }
};