找出最具竞争力的子序列(Leetcode 217场单周赛第2题)

1

题目分析

   这是第217场周赛的第二题,题目有一定的难度,希望小伙伴们能认真思考。

递归算法

这个题目可以使用递归进行求解,每次判断剩余的元素数目是否等于k,如果等于则将其全部加入结果,判断k是否等于0,如果是也可以作为递归出口

否则我们要保留k - 1个数,找到之前所有元素的最小值加入结果序列中。这里要说明的是保留k - 1个数的目的防止后面元素不满足k个。如[3,4,2,5,1]序列,k = 2,我们先选出序列的第一个元素,我们要保留2 - 1 = 1个元素,即保留1,从3,4,2,5中选择最小的作为序列的第一个元素,如果不保留,我们选择了1,那么后面就没有序列了,因此是不正确的。

为什么要找最小值呢?这也很容易理解,1,9,9,9的竞争力也大于2,0,0,0,因此我们有一种贪心的思想,能选最小的一定先选最小的。

每次递归都需要计算从当前元素到倒数第k个元素的最小值,算法的**时间复杂度为$O(n^2)$,空间复杂度为$O(n)$**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector>

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> res;
subQuestion(nums, res, 0, k);
return res;
}

void subQuestion(vector<int>& nums, vector<int>& res, int left, int k) {
if (k == 0) return;
if (nums.size() - left == k) {
for (int i = left; i < nums.size(); i++) res.push_back(nums[i]);
return;
}
int mini = nums[left], idx = left;
for (int i = left + 1; i < nums.size() - k + 1; i++) {
if (nums[i] < mini) mini = nums[i], idx = i;
}
res.push_back(mini);
subQuestion(nums, res, idx + 1, k - 1);
}
};

队列优化的迭代算法

能用递归求解的问题,很多都可以迭代求解,这个题目也一样,小伙伴们可以尝试一下如何将上面的递归改写为迭代算法。

上面的算法提交会TLE,因为数据量是1e5,因此不能使用$O(n^2)$的算法求解。我们想一下超时的问题出现在什么地方?

因为我们每次都要重新求解数组的最小值,浪费了大量的操作。这个题目类似于Leetcode239题,滑动窗口的相关题目,我们要求的最小值也是在滑动的,因此我们可以使用一个单调递增的队列保存滑动窗口的最小值。第一次从0到nums.size() - k + 1这个位置中计算单调递增队列。然后队头元素一定是最小值,因此将队头元素取出加入结果序列res中,然后窗口向下滑动

算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<vector>
#include<deque>

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> res;
deque<pair<int, int>> queue;
int begin = 0, end = nums.size() - k + 1;
while (k) {
for (int i = begin; i < end; i++) {
while (!queue.empty() && nums[i] < queue.back().first) queue.pop_back();
queue.push_back({ nums[i], i });
}
int val = queue.front().first, idx = queue.front().second;
res.push_back(val);
begin = end;
queue.pop_front();
k--;
end++;
}
return res;
}
};

本题的最妙解法是单调栈求解,时间复杂度和使用单调队列相同,但是代码非常简单。

我们不需要建立额外的单调队列保存最小值,可以直接将结果序列看成一个单调栈。向结果序列中添加元素,如果新加入的元素小于栈顶元素,则栈顶元素出栈,新元素入栈。维护一个单调递增的栈即可。前提是我们要保证剩余元素+栈内元素要大于等于k

算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<vector>

class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
while (!res.empty() && res.back() > nums[i] && nums.size() - i - 1 + res.size() >= k) res.pop_back();
if (res.size() < k) res.push_back(nums[i]);
}
return res;
}
};

刷题总结

  这个题目是典型的数据结构相关的算法题,难度适中,代码量不多不少,非常适合在面试中考察大家,因此小伙伴们一定要多多练习,自己实现一遍。

-------------本文结束感谢您的阅读-------------
0%