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 <= 1050 <= nums[i] <= 1091 <= k <= nums.length
Solution: Stack
Use a stack to track the best solution so far, pop if the current number is less than the top of the stack and there are sufficient numbers left. Then push the current number to the stack if not full.
Time complexity: O(n)
Space complexity: O(k)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: vector<int> mostCompetitive(vector<int>& nums, int k) { const int n = nums.size(); vector<int> ans(k); int c = 0; for (int i = 0; i < n; ++i) { while (c && ans[c - 1] > nums[i] && c + n - i - 1 >= k) --c; if (c < k) ans[c++] = nums[i]; } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public int[] mostCompetitive(int[] nums, int k) { int n = nums.length; int[] ans = new int[k]; int c = 0; for (int i = 0; i < n; ++i) { while (c > 0 && ans[c - 1] > nums[i] && c + n - i - 1 >= k) --c; if (c < k) ans[c++] = nums[i]; } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# Author: Huahua class Solution: def mostCompetitive(self, nums: List[int], k: int) -> List[int]: ans = [None] * k n = len(nums) c = 0 for i, x in enumerate(nums): while c and ans[c - 1] > x and c + n - i - 1 >= k: c -= 1 if c < k: ans[c] = x c += 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment