题目描述
给定一个整数数组 nums
和一个正整数 k
,返回长度为 k
且最具 竞争力 的 nums
子序列。
数组的子序列是从数组中删除一些元素(可能不删除元素)得到的序列。
在子序列 a
和子序列 b
第一个不相同的位置上,如果 a
中的数字小于 b
中对应的数字,那么我们称子序列 a
比子序列 b
(相同长度下)更具 竞争力。 例如,[1,3,4]
比 [1,3,5]
更具竞争力,在第一个不相同的位置,也就是最后一个位置上,4
小于 5
。
样例
输入:nums = [3,5,2,6], k = 2
输出:[2,6]
解释:在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中,[2,6] 最具竞争力。
输入:nums = [2,4,3,3,5,4,9,6], k = 4
输出:[2,3,3,4]
限制
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
1 <= k <= nums.length
算法1
(线段树) $O(n + k \log n)$
- 在原数组上构造区间最小值的线段树(如果最小值相同,则下标小的更优)。
- 共查询 $k$ 次,第一次查询
[0, n - k]
的最小值,同时记录last
为当次查询的最小值的下标加 1。之后每次查询,都查询[last, n + i - 1 - k]
的最小值,同时更新last
。
时间复杂度
- 建树的时间复杂度为 $O(n)$,每次查询只需要 $O(\log n)$ 的时间,故总时间复杂度为 $O(n + k \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储线段树和答案数组。
C++ 代码
class Solution {
private:
vector<pair<int, int>> m;
void build(int l, int r, int rt, const vector<int> &nums) {
if (l == r) {
m[rt] = make_pair(nums[l], l);
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1, nums);
build(mid + 1, r, rt << 1 | 1, nums);
m[rt] = min(m[rt << 1], m[rt << 1 | 1]);
}
pair<int, int> query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R)
return m[rt];
int mid = (l + r) >> 1;
pair<int, int> res(INT_MAX, -1);
if (L <= mid) res = min(res, query(L, R, l, mid, rt << 1));
if (mid < R) res = min(res, query(L, R, mid + 1, r, rt << 1 | 1));
return res;
}
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
const int n = nums.size();
m.resize((n + 10) << 2, make_pair(INT_MAX, -1));
build(0, n - 1, 1, nums);
vector<int> ans;
int last = 0;
for (int i = k; i >= 1; i--) {
pair<int, int> t = query(last, n - i, 0, n - 1, 1);
ans.push_back(t.first);
last = t.second + 1;
}
return ans;
}
};
算法2
(单调队列) $O(n)$
- 维护一个单调递增的队列,队列中记录的都是候选的值。
- 如果当前的值小于队尾的值,则队尾出队。直到满足单调性,当前值进队。
- 当 $i$ 到达必须从队头出队时(即队头已经确定了时),队头出队,并记录答案。
时间复杂度
- 每个元素最多入队一次,出队一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储单调队列和答案数组。
C++ 代码
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
const int n = nums.size();
deque<int> q;
vector<int> ans;
for (int i = 0; i < n; i++) {
while (!q.empty() && nums[i] < nums[q.back()])
q.pop_back();
q.push_back(i);
if (i >= n - k) {
ans.push_back(nums[q.front()]);
q.pop_front();
}
}
return ans;
}
};
C++ 代码(改进后)
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
const int n = nums.size();
vector<int> ans;
for (int i = 0; i < n; i++) {
while (!ans.empty() && ans.size() + n - i > k && nums[i] < ans.back())
ans.pop_back();
if (ans.size() < k)
ans.push_back(nums[i]);
}
return ans;
}
};
“如果当前的值大于队尾的值,则队尾出队。”貌似有个笔误,应是“小于”而非“大于”吧?
已修正 hh~