当前位置：首页 > ops >正文

【贪心算法】day2

ops 2025/8/25 13:54:30

📝前言说明：

本专栏主要记录本人的贪心算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）；（4）贪心策略正确性的 “证明”
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行其他贪心算法题目的学习

点击链接	开始学习
贪心day1	贪心day2
贪心day3	贪心day4
贪心day5	贪心day6
贪心day7	贪心day8
贪心day9	贪心day10

也可以点击下面连接，学习其他算法

点击链接	开始学习
优选专题	动态规划
递归、搜索与回溯	贪心算法

题目

179. 最大数
- 优质解
- 证明
376. 摆动序列
- 优质解
300. 最长递增子序列
- 优质解

179. 最大数

题目链接：https://leetcode.cn/problems/largest-number/description/
在这里插入图片描述

优质解

思路：

该题其实就是一个排序问题，排序问题本质是：选择两个数，然后按规则决定两个数的先后顺序
本题：对于a和b，我们尝试获得 ab 和 ba 的组合，哪个组合大，则为正确的排序（这就是本题的贪心策略）
然后，sort的时候按我们的规则排序即可

细节：

我们可以先把数字转换成字符串，然后拼接字符串，比较字典序
全为 0 的特殊情况

代码：

class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> strs;for(auto x: nums) strs.emplace_back(to_string(x));auto rule = [](const string& s1, const string& s2){return s1 + s2 > s2 + s1; // 返回true代表优先级高};sort(strs.begin(), strs.end(), rule);string ans = "";for(auto s: strs)ans += s;return ans[0] == '0'? string("0") : ans;}
};

时间复杂度： $O (k \cdot n l o g n)$ ，k 为字符串平均长度，拼接操作时间复杂度为 $O (k)$
空间复杂度： $O (nk)$

证明

来自Leetcode官方题解答案：
在这里插入图片描述

376. 摆动序列

题目链接：https://leetcode.cn/problems/wiggle-subsequence/description/
在这里插入图片描述

优质解

思路：

贪心策略：以序列结束位置为基准，每次只考虑下一个元素是否会让此序列变得更长
下一个位置有两种情况 > 或 < ，代表两个不同状态结尾的序列
且 > 的up 序列的是在前一个 down 序列的长度上 +1，如果出现连续的 >，只会 +1 一次（正确性保证 1）
因为我们始终记录了两种状态的序列（即：全部状态），并且每次都是在原来最优解的基础上+1，所以每次的局部最优就是全局最优

代码：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if(n == 1) return 1;int up = 1, down = 1;for(int i = 1; i < nums.size(); i++){if(nums[i] > nums[i - 1])up = down + 1;if(nums[i] < nums[i - 1])down = up + 1;}return max(up, down);}
};

时间复杂度： $O (n)$
空间复杂度： $O (1)$

300. 最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
在这里插入图片描述

优质解

思路：

贪心 + 二分

回想动态规划：如果新插入的数字比原来最长子序列的最后一个数字大，则可以接入（所以我们只关注子序列的最后一个元素和新插入的元素的大小）
用end[i] 表示：长度为 i 的子序列的最后一个元素的大小
每次插入数时，用二分查找找到最佳的插入位置
- 如果可以接在目前最长的子序列后面，则代表：变得更长
- 如果不能，则可能更新（变小）前面某一子序列的结尾的数

代码：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> end; // end[i]: 长度为 i 的序列的结尾的元素end.push_back(nums[0]);for(int i = 1; i < n; i++){if(nums[i] > end.back())end.push_back(nums[i]);else{// 二分查找int left = 0, right = end.size() - 1;while(left < right){int mid = (left + right) >> 1;if(end[mid] < nums[i])left = mid + 1;elseright = mid;}end[left] = nums[i];}} return end.size();}
};