【C++单调栈】1673. 找出最具竞争力的子序列|1802
本文涉及的基础知识点
C++单调栈
LeetCode1673. 找出最具竞争力的子序列
给你一个整数数组 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 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length
单调栈
本题
⟺
\iff
⟺ 长度为k的字典序最小的子序列。
如果栈中的字符数+ 剩余字符数等于k,则不能出栈,否则长度小于k。
否则:如果当前元素小于栈顶元素出栈,直到栈为空或栈顶元素小于等于当前栈。
如果栈的长度大于k,出栈到k。
从栈底到栈顶就是结果。
如果当前元素小于栈顶元素,则替换后,字典序一定变小。
代码
核心代码
class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
vector<int> sta;
const int N = nums.size();
for (int i = 0; i <N ;i++) {
while (sta.size() && (sta.back() > nums[i]) && (N - i + sta.size() > k)) {
sta.pop_back();
}
sta.emplace_back(nums[i]);
}
return vector<int>(sta.begin(), sta.begin() + k);
}
};
单元测试
vector<int> nums;
int k;
TEST_METHOD(TestMethod1)
{
nums = { 3,2,1 }, k = 3;
auto res = Solution().mostCompetitive(nums, k);
AssertEx({3,2,1 }, res);
}
TEST_METHOD(TestMethod2)
{
nums = { 3,2,1 }, k = 2;
auto res = Solution().mostCompetitive(nums, k);
AssertEx({2,1 }, res);
}
TEST_METHOD(TestMethod3)
{
nums = { 3,2,1 }, k = 1;
auto res = Solution().mostCompetitive(nums, k);
AssertEx({ 1 }, res);
}
TEST_METHOD(TestMethod4)
{
nums = { 1,2,3 }, k = 1;
auto res = Solution().mostCompetitive(nums, k);
AssertEx({ 1 }, res);
}
TEST_METHOD(TestMethod11)
{
nums = { 3, 5, 2, 6 }, k = 2;
auto res = Solution().mostCompetitive(nums, k);
AssertEx({ 2,6 }, res);
}
TEST_METHOD(TestMethod12)
{
nums = { 2,4,3,3,5,4,9,6 }, k =4;
auto res = Solution().mostCompetitive(nums, k);
AssertEx({ 2,3,3,4 }, res);
}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。