题目描述
给你一个整数数组 nums
和一个正整数k
,返回长度为 k
且最具 竞争力 的 nums
子序列。
数组的子序列是从数组中删除一些元素(可能不删除元素)得到的序列。
在子序列a
和子序列b
第一个不相同的位置上,如果a
中的数字小于b
中对应的数字,那么我们称子序列a
比子序列 b
(相同长度下)更具 竞争力 。 例如,[1,3,4]
比 [1,3,5]
更具竞争力,在第一个不相同的位置,也就是最后一个位置上,4
小于 5
。
样例
示例1
输入:nums = [3,5,2,6], k = 2
输出:[2,6]
解释:在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中,[2,6] 最具竞争力。
示例2
输入:nums = [2,4,3,3,5,4,9,6], k = 4
输出:[2,3,3,4]
算法1
(单调栈) $O(n + k)$
- 这题的暴力思路是显然的: 在 $[0, (n-k+1)]$(因为尾巴要至少留出足够多的数字去凑答案)之间找到最小的数的第一个位置
idx
作为ans
中的第0
个数. - 在
idx + 1
到(n - (k - 1 )+ 1)
之间找到最小的数的第一个位置作为ans
中的第1
个数 - 重复 步骤$1$, $2$。直到凑满
k
个. - 这个思路的复杂度是$n^2$的,因此我们需要对他做优化.
5 一个比较显然的做法是使用线段树维护区间最小值,这个思路的代码会在后面补上。 - 观察到搜索区间的左端点
idx
是一直往右移动的,具有单调性,因此我们可以考虑维护一个单调不递减的栈,前提要求是这个栈的长度加上剩余待枚举的数量和超过k
个。 - 直接用
vector
模拟栈即可
时间复杂度
- 遍历整个数组需要$O(n)$的时间
- 维护单调栈最坏需要
k
次比较(清空) - 故总时间复杂度为 $O(n + k)$
C++ 代码
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> ans;
int n = nums.size();
for(int i = 0; i < n; i++){
while(ans.size() && (n - i) + ans.size() > k && nums[i] < ans.back()){
ans.pop_back();
}
if(ans.size() < k) ans.push_back(nums[i]);
}
return ans;
}
};
算法2
(线段树) $O(nlog(n))$
参考解法1
的思路,使用线段树加速找到ans[i]
的对应区间的最小值.
- 这题的暴力思路是显然的: 在 $[0, (n-k+1)]$之间找到最小的数的第一个位置
idx
作为ans
中的第0
个数. - 在
idx
到(n - (k - 1) + 1)
之间找到最小的数的第一个位置作为ans
中的第1
个数 - 重复 步骤$1$, $2$。直到凑满
k
个. - 这个思路的复杂度是$n^2$的,因此我们需要对他做优化.
- 使用线段树加速找到
ans[i]
的所在原数组区间的最小值。 线段树记录了区间最小值
,最小值所在的位置
。 - 由于个人习惯,我在节点中记录了左右端点,静态线段树这里其实是不需要的。
时间复杂度
- 需要 $O(n)$的时间预处理线段树
- 需要 $O(klog(n))$的时间进行
k
次查询找到区间最小值
故总时间复杂度为$O(klog(n))$
C++ 代码
struct Node{
int l, r, v, idx;
}tr[(int)1e5 * 4 + 10];
class Solution {
public:
vector<int> nums;
void pushup(Node& u, Node& left, Node& right){
u.v = min(left.v, right.v);
u.idx = left.v <= right.v ? left.idx : right.idx;
}
void build(int u, int l, int r){
tr[u] = {l, r, 0x3f3f3f3f, 0};
if(l >= r) {
tr[u] = {l, r, nums[l], l};
return;
}
int mid = (l + r) >> 1;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
pushup(tr[u], tr[u * 2], tr[u * 2 + 1]);
}
Node query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
else{
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) return query(u * 2, l, r);
else if(l > mid) return query(u * 2 + 1, l, r);
else{
Node left = query(u * 2, l, r);
Node right = query(u * 2 + 1, l, r);
Node ans = {0, 0, 0, 0};
pushup(ans, left, right);
return ans;
}
}
}
vector<int> mostCompetitive(vector<int>& _nums, int k) {
_nums.insert(_nums.begin(), 0x3f3f3f3f);
nums = _nums;
int n = nums.size() - 1;
build(1, 1, n);
vector<int> ans(k);
int idx = 1;
int K = k;
Node temp = query(1, 1, n);
for(int i = 0; i < K; i++){
Node temp = query(1, idx, n - k + 1);
ans[i] = temp.v;
idx = temp.idx + 1;
k--;
}
return ans;
}
};
算法3
(排序 双指针双向夹逼) $O(nlog(n))$
- 我们存储
{nums[i], i}
到数组a
中,进行双关键字排序 - 定义双指针
idx
,idx2
分别表示idx
表示目前已经处理过的数的最后一个数在原数组中的可行最小位置,从0
开始往后遍历。idx2
表示剩余没有确定的数中,已经可以确定的最小位置, 即nums[idx2...n - 1]
是可以确定的答案的后缀。初始化为数组长度,即没有一个剩余数字是确定的
- 定义参数
rem
表示剩余未排数字,初始化为k
. - 从前往后遍历
a
数组, 由于a
是从小到大排序的,那么- 如果当前遍历到的数字可以放到
k - rem
处(当前答案更新到的位置),直接放在k-rem
处,rem--
- 如果当前遍历到的数字放到
k-rem
处会导致剩下的数字不够构成长度为k
的答案,那么我们尝试更新idx2
。 - 当发现 已经摆好的数字个数+后缀长度等于
k
时,跳出循环,并把后缀补到ans
中。
这里的4.1和4.2概括一下就是 “非前即后”。遍历到的这个数,它在原数组中的位置只有以下三种情况
1.属于前缀(即有更小的数字提前卡在了这个位置上) - 无视
2.属于后缀(即idx2 - n
之间) - 无视
3.在中间:
* 如果添加到前缀中之后,该位置在原数组中后面剩下的数无法凑够答案,那么就把他拿来更新后缀
* 否则由于a
是有序的,所以它应该直接添加到前缀中
- 如果当前遍历到的数字可以放到
- 举个简单的例子
[3 2 1 4 5]
K = 4
排完之后[1 2 3 4 5]
- 遍历
[1 2 3 4 5]
,1
在原数组的下标是2
,那么2-4
位置的那几个数1 4 5
一定是答案的后缀了. - 下一个数字是2,2在原数组的位置是1,1-4是够拼成k个数的 那么ans的第一个数字肯定是2.
- 由于次数已有答案(前缀)的数量是
1
个,后缀长度是3
,刚好可以凑成k=4
个数,那么把后缀拼接到ans
后面就是我们的答案。
- 遍历
时间复杂度
- 需要 $O(n)$的时间预处理
{nums[i], [i]}
数组a
- 需要 $O(nlog(n))$的时间对
a
排序 - 需要 $O(n)$的时候遍历数组移动指针更新答案
故总时间复杂度为$O(nlog(n))$
C++ 代码
pair<int, int> a[(int)1e5+10];
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
int idx = 0, n = nums.size(), rem = k, idx2 = nums.size();
vector<int> ans(k);
for(int i = 0; i < n; i++) a[i] = {nums[i], i};
sort(a, a + n);
for(auto p : a){
if(p.second >= idx && p.second <= n - rem ){
ans[k - rem] = p.first;
rem --;
idx = p.second + 1;
}else if(p.second > n - rem && p.second < idx2){
idx2 = p.second;
}
if(rem - (n - idx2) == 0) break;
}
for(int i = idx2; i < n; i++){
ans[k - (n - i)] = nums[i];
}
return ans;
}
};