题目描述
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 <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length
算法1
(单调栈) $O(n)$
首先将题目转化成更直观的问题:寻找长度为k
的字典序最小的子序列。字典序最小意味着越小的数字应该排在高位,对于当前数字nums[i]
,假设现在已经找到了一个子序列长度为k
,现在我们想让nums[i]
排在这个子序列的第pos
个位置,那么意味着子序列里从pos + 1
到k - 1
的数字应该被排除掉,这也就意味着在原数组里位于nums[i]
之前位置的数字被排除掉并且不会被使用,所以想到采用单调栈求解。
但是注意,单调栈里只是近似从栈底到栈顶单增,因为考虑如果对于nums[i]
及其后面的数字,和之前已经选出来的数字恰好为k
个,此时则不一定是单增。那么判别的一种办法就是用dropNum
记录有多少个数字被丢弃掉了,如果dropNum
到了n - k
,那么从当前数字开始及以后的都直接入栈即可。如果dropNum
还未到n - k
,则延续单调栈的做法。
于是问题集中在如何处理dropNum
,首先当延续单调栈的做法时候,从栈内弹出的数字肯定是要被丢弃的,另外就是栈内的元素已经满掉,并且当前数字不满足进栈条件,也会被丢弃。
时间复杂度$O(n)$,空间复杂度$O(n)$。
C++ 代码
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = nums.size();
if (n == k) return nums;
int dropNum = 0;
stack<int> s;
for (int i = 0; i < n; ++i) {
if ((int)s.size() >= k && nums[i] >= s.top()) {
++dropNum;
continue;
}
if (dropNum >= n - k) s.emplace(nums[i]);
else {
if (s.empty()) s.emplace(nums[i]);
else {
while (!s.empty() && dropNum < n - k && nums[i] < s.top()) {
s.pop();
++dropNum;
}
s.emplace(nums[i]);
}
}
}
vector<int> res(k);
int pos = k - 1;
while (!s.empty()) {
res[pos--] = s.top(); s.pop();
}
return res;
}
};