七. 贪心算法
文章目录
- 七. 贪心算法
- 1. 605 种花问题
- 2. 121 买卖股票的最佳时机
- 3. 561 数组拆分
- 4. 455 分发饼干
- 5. 575 分糖果
- 6. 135 分发糖果
- 7. 409 最长回文串
- 8. 621 任务调度器
- 9. 179 最大数
- 10. 56 合并区间
- 11. 57 插入区间
- 13. 452 用最少数量的箭引爆气球
- 14. 435 无重叠区间
- 15. 646 最长数对链
- 16. 406 按照身高重建队列
- 17. 48 旋转图像
- 18. 169 多数元素
- 19. 215 数组中的第k个最大元素
- 20. 75 颜色分类
- 21. 324 摆动顺序II
- 22. 517 超级洗衣机[未解]
- 23. 649 Dota2 参议院
- 24. 678 有效的括号字符串
- 25. 420 强密码检验器
- 26. 53 最大子数组和
- 27. 134 加油站
- 28. 581 最短无序连续子数组
- 29. 152 乘积最大子数组
- 30. 334 递增的三元子序列
- 31. 376 摆动序列
- 32. 659 分割数组为连续子序列
- 33. 343 整数拆分
- 34. 496 下一个更大元素I
- 35. 503 下一个更大的元素||
- 36. 456 132模式
- 37. 316 去除重复字母
- 38. 402 移掉k位数字
- 39. 321 拼接最大数
- 40. 84 柱状图中最大的矩形
- 41. 85 最大矩形
- 题目分类 题目编号
- 数组与贪心算法 605、121、122、561、455、575、135、409、621、179、56、57、228、452、435、646、406、48、169、215、75、324、517、649、678、420
- 子数组与贪心算法 53、134、581、152
- 子序列与贪心算法 334、376、659
- 数字与贪心 343
- 单调栈法 496、503、456、316、402、321、84、85
1. 605 种花问题
解法：贪心算法
我们直接遍历数组flowerbed，对于每个位置 iii，如果flowerbed[i]=0，并且其左右相邻位置都为 0，则我们可以在该位置种花，否则不能。最后我们统计可以种下的花的数量，如果其不小于 n，则返回 true，否则返回 false。
代码：
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int len=flowerbed.size();
if(n==0)
return true;
for(int i=0;i<len;i++){
if(i==0&&flowerbed[i]==0)
{
if(len==1||flowerbed[i+1]==0){
n--;
flowerbed[i]=1;
}
}
else if(i==len-1&&flowerbed[i]==0){
if(flowerbed[i-1]==0){
n--;
flowerbed[i]=1;
}
}
else{
if(flowerbed[i]==0&&flowerbed[i-1]==0&&flowerbed[i+1]==0){
n--;
flowerbed[i]=1;
}
}
if(n==0)
return true;
}
return false;
}
};
注意有种简洁的代码描述方式，比上述代码来的简洁的多
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int m = flowerbed.size();
for (int i = 0; i < m; ++i) {
int l = i == 0 ? 0 : flowerbed[i - 1];
int r = i == m - 1 ? 0 : flowerbed[i + 1];
if (l + flowerbed[i] + r == 0) {
flowerbed[i] = 1;
--n;
}
}
return n <= 0;
}
};
时间复杂度：O(n)，其中 n 是数组 flowerbed的长度。只需要遍历数组一次。
空间复杂度: O(1)。
2. 121 买卖股票的最佳时机
解法1：一次遍历
假设给定的数组为：[7, 1, 5, 3, 6, 4]
我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？
显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了，在题目中，我们只要用一个变量记录一个历史最低价格 minPrice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minPrice。
因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len<2)
return 0;
int minPrice=prices[0],maxProfit=0;
for(int p:prices){
maxProfit=max(maxProfit,p-minPrice);
minPrice=min(p,minPrice);
}
return maxProfit;
}
};
时间复杂度：O(n) 只遍历了一次
空间复杂度：O(1) 只使用了常量个变量。
解法2: 动态规划
思路：题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用 动态规划 的方法来解决。
买卖股票有约束，根据题目意思，有以下两个约束条件：
条件 1：你不能在买入股票前卖出股票；
条件 2：最多只允许完成一笔交易。
因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中。
dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数。换种说法：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润。其中：
j = 0，表示当前不持股；
j = 1，表示当前持股。
注意：下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]。
使用「现金数」这个说法主要是为了体现 买入股票手上的现金数减少，卖出股票手上的现金数增加 这个事实；
「现金数」等价于题目中说的「利润」，即先买入这只股票，后买入这只股票的差价；
推导状态转移方程：
dp[i][0]：规定了今天不持股，有以下两种情况：
-
昨天不持股，今天什么都不做；
-
昨天持股，今天卖出股票（现金数增加），
dp[i][1]：规定了今天持股，有以下两种情况：
- 昨天持股，今天什么都不做（现金数与昨天一样）；
- 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。
代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len<2)
return 0;
int dp[len][2];
// dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
// dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数
dp[0][0]=0;
dp[0][1]=-prices[0];
for(int i=1;i<len;i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]=max(dp[i-1][1],-prices[i]);
}
return dp[len-1][0];
}
};
- 时间复杂度：O(N)，遍历股价数组可以得到最优解；
- 空间复杂度：O(N)，状态数组的长度为 N。
3. 561 数组拆分
解法：排序
我们先对数组进行排序。由于每两个数，我们只能选择当前小的一个进行累加。因此我们猜想应该从第一个位置进行选择，然后隔一步选择下一个数。这样形成的序列的求和值最大。
我们用反证法来证明下，为什么这样选择的序列的求和值一定是最大的：
猜想：对数组进行排序，从第一个位置进行选择，然后隔一步选择下一个数。这样形成的序列的求和值最大（下图黑标，代表当前被选择的数字）。
之所以我们能这么选择，是因为每一个被选择的数的「下一位位置」都对应着一个「大于等于」当前数的值（假设位置为 k ），使得当前数在 min(a,b) 关系中能被选择（下图红标，代表保证前面一个黑标能够被选择的辅助数）。
假如我们这样选择的序列求和不是最大值，那么说明至少我们有一个值选错了，应该选择更大的数才对。
那么意味着我们「某一位置」的黑标应该从当前位置指向更后的位置。
PS. 因为要满足 min(a, b) 的数才会被累加，因此每一个红标右移（变大）必然导致原本所对应的黑标发生「同样程度 或 不同程度」的右移（变大）
这会导致我们所有的红标黑标同时往后平移。
最终会导致我们最后一个黑标出现在最后一位，这时候最后一位黑标不得不与我们第 k 个位置的数形成一对。
我们看看这是求和序列的变化（ k 位置前的求和项没有发生变化，我们从 k 位置开始分析）：
原答案 = nums[k] + nums[k + 2] + … + nums[n - 1]
调整后答案 = nums[k + 1] + nums[k + 3] + … + nums[n - 2] + min(nums[n], nums[k])
由于 min(nums[n], nums[k]) 中必然是 nums[k] 被选择。因此：
调整后答案 = nums[k] + nums[k + 1] + nums[k + 3] + … + nums[n - 2]
显然从原答案的每一项都「大于等于」调整后答案的每一项，因此不可能在「假想序列」中通过选择别的更大的数得到更优解，假想得证。
代码：
class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
int sum=0;
for(int i=0;i<nums.size()-1;i+=2){
sum+=min(nums[i],nums[i+1]);
}
return sum;
}
};
时间复杂度：O(nlogn)即对数组nuts进行排序的时间复杂度
空间复杂度：O(logn) 排序所需要使用的栈空间
4. 455 分发饼干
解法：双指针+贪心
为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，且对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干。证明如下。
假设有 m 个孩子，胃口值分别是 g 1 g_1 g1到 g m g_m gm，有 n块饼干，尺寸分别是 s 1 s_1 s1到 s n s_n sn，满足 g i ≤ g i + 1 g_i \le g_{i+1} gi≤gi+1和 s j ≤ s j + 1 s_j \le s_{j+1} sj≤sj+1 ，其中 1 ≤ i < m 1 \le i < m 1≤i<m， 1 ≤ j < n 1 \le j < n 1≤j<n。
假设在对前 i−1 个孩子分配饼干之后，可以满足第 i 个孩子的胃口的最小的饼干是第 j 块饼干，即 s j s_j sj是剩下的饼干中满足 g i ≤ s j g_i \le s_j gi≤sj的最小值，最优解是将第 j块饼干分配给第 i个孩子。如果不这样分配，考虑如下两种情形：
如果 i<m 且 g i + 1 ≤ s j g_{i+1} \le s_j gi+1≤sj也成立，则如果将第 j 块饼干分配给第 i+1个孩子，且还有剩余的饼干，则可以将第 j+1 块饼干分配给第 iii 个孩子，分配的结果不会让更多的孩子被满足；
如果 j<n，则如果将第 j+1 块饼干分配给第 i个孩子，当 g i + 1 ≤ s j g_{i+1} \le s_j gi+1≤sj时，可以将第 j块饼干分配给第 i+1 个孩子，分配的结果不会让更多的孩子被满足；当 g i + 1 > s j g_{i+1}>s_j gi+1>sj时，第 j 块饼干无法分配给任何孩子，因此剩下的可用的饼干少了一块，因此分配的结果不会让更多的孩子被满足，甚至可能因为少了一块可用的饼干而导致更少的孩子被满足。
基于上述分析，可以使用贪心的方法尽可能满足最多数量的孩子。
首先对数组 g 和 s 排序，然后从小到大遍历 g 中的每个元素，对于每个元素找到能满足该元素的 s 中的最小的元素。具体而言，令 i 是 g 的下标，j是 s的下标，初始时 i 和 j 都为 0，进行如下操作。
对于每个元素 g[i]，找到未被使用的最小的 j使得 g [ i ] ≤ s [ j ] g[i] \le s[j] g[i]≤s[j]，则 s[j] 可以满足 g[i]。由于 g 和 s 已经排好序，因此整个过程只需要对数组 g 和 s 各遍历一次。当两个数组之一遍历结束时，说明所有的孩子都被分配到了饼干，或者所有的饼干都已经被分配或被尝试分配（可能有些饼干无法分配给任何孩子），此时被分配到饼干的孩子数量即为可以满足的最多数量。
代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int count=0;
int sizeG=g.size();
int sizeS=s.size();
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int i=0;
int j=0;
while(i<sizeG&&j<sizeS){
if(g[i]>s[j]){
j++;
}
else{
i++;
j++;
count++;
}
}
return count;
}
};
时间复杂度：O(mlogm+nlogn)，其中 m 和 n 分别是数组 g 和 s 的长度。对两个数组排序的时间复杂度是 O(mlogm+nlogn)，遍历数组的时间复杂度是 O(m+n)O(m+n)O(m+n)，因此总时间复杂度是 O(mlogm+nlogn)。
空间复杂度：O(logm+logn)，其中 m 和 n 分别是数组 g和 s的长度。空间复杂度主要是排序的额外空间开销。
5. 575 分糖果
解法：贪心
设糖果的数量为n，因为最多只能分到一半的糖果，答案不会超过 n 2 \frac{n}{2} 2n;设置糖果的种类个数为numCandyType，答案也不会超过numCandyType。
利用set对candyType进行去重，得到numCandyType的糖果种类个数；
很显然，如果 n 2 > n u m T y p e \frac{n}{2}>numType 2n>numType；最多只能吃numType种类的糖果；否则 n 2 ≤ n u m T y p e \frac{n}{2}\leq numType 2n≤numType，则最多也只能吃到 numType种的糖果
注意使用unordered_set的性能在此时大于set
- 底层数据结构：
std::set是基于平衡二叉搜索树（通常是红黑树）实现的，它保持元素有序，因此插入、删除和查找的时间复杂度都是 O(log n)。std::unordered_set是基于哈希表实现的，它使用哈希函数将元素映射到桶中，插入、删除和查找的平均时间复杂度是 O(1)。- 性能比较：
- 在大多数情况下，
std::unordered_set的操作更快，因为哈希表通常能够提供更快的查找和插入操作。- 然而，在某些特定情况下（例如数据量较小或有序插入），
std::set的性能可能更好，因为它不需要处理哈希冲突，而且红黑树的有序性可能在某些操作上产生优势。- 迭代顺序：
std::set保持元素有序，因此在迭代时，元素以升序顺序出现。std::unordered_set不保持元素的顺序，迭代时元素的顺序是不确定的。- 选择适当容器：
- 选择使用哪种容器应取决于你的使用场景和需求。如果你需要有序性，并且能够接受较慢的插入和查找，可以选择
std::set。如果你更关注插入和查找的性能，并且不需要有序性，可以选择std::unordered_set。
代码：
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
std::set<int>CandyTypeSet(candyType.begin(),candyType.end());
int numCandyType=CandyTypeSet.size();
int n=candyType.size();
if(n/2>numCandyType)
{
return numCandyType;
}
return n/2;
}
};
时间复杂度：O(n)，其中 n 是数组 CandyTypeSet 的长度。
空间复杂度：O(n)。CandyTypeSet的哈希表需要O(n) 的空间。
6. 135 分发糖果
解法一：贪心算法
规则定义： 设学生 A 和学生 B 左右相邻，A在 B 左边；
左规则： 当 ratings[B]>ratings[A]时候，B 的糖比 A 的糖数量多。
右规则： 当 ratings[A]>ratings[B]时，A 的糖比 B 的糖数量多。
相邻的学生中，评分高的学生必须获得更多的糖果 等价于 所有学生满足左规则且满足右规则。
根据以上规则，我们可以从左向右按照左规则遍历一遍，再从右向左按照右规则遍历一遍；之后每次都取位置i的糖果最大数目，可以保证即满足左规则又满足了右边规则；
算法流程：
先从左至右遍历学生成绩 ratings，按照以下规则给糖，并记录在 left 中，先给所有学生 1颗糖；
若 ratings[i]>ratings[i−1]，则第 i名学生糖比第 i−1 名学生多 1 个。
若 ratings[i]<=ratings[i−1] ，则第 i名学生糖数量不变。（交由从右向左遍历时处理。）
经过此规则分配后，可以保证所有学生糖数量 满足左规则 。
同理，在此规则下从右至左遍历学生成绩并记录在 right 中，可以保证所有学生糖数量 满足右规则 。
最终，取以上 2轮遍历 left 和 right 对应学生糖果数的最大值 ，这样则 同时满足左规则和右规则 ，即得到每个同学的最少糖果数量。
【此过程可以在从右往左遍历右规则时完成】
代码：
class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
int left[n];
std::fill(left,left+n,1);
int right[n];
std::fill(right,right+n,1);
for(int i=1;i<n;i++){
if(ratings[i]>ratings[i-1]){
left[i]=left[i-1]+1;
}
}
int count=left[n-1];
for(int i=n-2;i>=0;i--){
if(ratings[i]>ratings[i+1]){
#从右边往左时候，递归记录的是最后一个位置的糖果个数，一直递归影响到前面位置的糖果个数
right[i]=right[i+1]+1;
}
count+=max(left[i],right[i]);
}
return count;
}
};
时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度：O(n)，其中 n 是孩子的数量。我们需要保存所有的左规则对应的糖果数量。
解法二：常数空间遍历
参考力扣官方题解：135. 分发糖果 - 力扣（LeetCode）
注意到糖果总是尽量少给，且从 11开始累计，每次要么比相邻的同学多给一个，要么重新置为 1。依据此规则，我们可以画出下图：
-
上述为例子[1,3,5,2,3,3]的最后的解
-
其中相同颜色的柱状图的高度总恰好为 1,2,3…。
而高度也不一定一定是升序，也可能是 …3,2,1的降序：
-
上述为数组[1,3,5,3,2,2]的解
-
注意到在上图中，对于第三个同学，他既可以被认为是属于绿色的升序部分，也可以被认为是属于蓝色的降序部分。因为他同时比两边的同学评分更高。我们对序列稍作修改：
- 注意到右边的升序部分变长了，使得第三个同学不得不被分配 4个糖果。
- 依据前面总结的规律，我们可以提出本题的解法。我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为 pre：
- 如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 pre+1 个糖果即可。
- 否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中所有的同学都再多分配一个糖果，以保证糖果数量还是满足条件。
- 我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。
- 同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。
- 这样，我们只要记录当前递减序列的长度 dec，最近的递增序列的长度 inc 和前一个同学分得的糖果数量 pre 即可。
代码：
class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
int ret=1;
int inc=1,dec=0,pre=1;
for(int i=1;i<n;i++){
if(ratings[i]>=ratings[i-1]){
//将递减序列的个数清0
dec=0;
pre=ratings[i]==ratings[i-1]?1:pre+1;
ret+=pre;
inc=pre;
}else{
//递减序列，记录递减序列的值
dec++;
//标志位置相同，如123321，此时递增序列的末尾3必须加1，合并到递减序列中
if(dec==inc){
dec++;
}
ret+=dec;
//pre还原为初始值1，为了后续递增准备
pre=1;
}
}
return ret;
}
};
时间复杂度：O(n)，其中 n 是孩子的数量。我们需要遍历两次数组以分别计算满足左规则或右规则的最少糖果数量。
空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
7. 409 最长回文串
解法：贪心算法
回文串是一个正着读和反着读都一样的字符串。以回文中心为分界线，对于回文串中左侧的字符 ch，在右侧对称的位置也会出现同样的字符。例如在字符串 “abba” 中，回文中心是 “ab|ba” 中竖线的位置，而在字符串 “abcba” 中，回文中心是 “ab©ba” 中的字符 “c” 本身。我们可以发现，在一个回文串中，只有最多一个字符出现了奇数次，其余的字符都出现偶数次。
我们可以将每个字符使用偶数次，使得它们根据回文中心对称。在这之后，如果有剩余的字符，我们可以再取出一个，作为回文中心。
算法
- 首先利用letterToCount统计字符串中每个字符出现的个数，设置结果为result,然后遍历letterToCount的value
- 如果value是偶数，则直接与result相加；如果value是奇数，则将value-1与result相加，并且flag设置为1
- 最后若flag为1，就说明字符中有单个的字符存在，可以作为回文串中的中心点，因此将result++;
class Solution {
public:
int longestPalindrome(string s) {
unordered_map<char,int>letterToCount;
for(auto letter:s){
letterToCount[letter]++;
}
int result=0;
int flag=0;
for(auto it=letterToCount.begin();it!=letterToCount.end();it++){
if(it->second%2==0){
result+=it->second;
}
else{
result+=(it->second-1);
flag=1;
}
}
if(flag)
result++;
return result;
}
};
时间复杂度：O(N)，其中 N 为字符串 s 的长度。我们需要遍历每个字符一次。
空间复杂度：O(S)，其中 S 为字符集大小，在c++中使用哈希映射，最多只会存储 52 个（即小写字母与大写字母的数量之和）键值对。
8. 621 任务调度器
解法：桶思想
-
先考虑最为简单的情况：假设只有一类任务，除了最后一个任务以外，其余任务在安排后均需要增加 n 个单位的冻结时间。设这类任务的个数为max，则需要构造max个桶，每个桶最多保存n+1个任务。
-
将任务数记为 m 个，其中前m−1 个任务均要消耗n+1 的单位时间，最后一个任务仅消耗 1 个单位时间，即所需要的时间为 (n+1)×(m−1)+1。
-
当存在多个任务时，由于每一类任务都需要被完成，因此本质上我们最需要考虑的是将数量最大的任务安排掉，其他任务则是间插其中。
假设数量最大的任务数为 max，共有 tot 个任务数为 max 的任务种类。
实际上，当任务总数不超过 (n+1)×(max−1)+tot （注意tot就是最后一行的任务数）时，我们总能将其他任务插到空闲时间中去，不会引入额外的冻结时间（下左图）；而当任务数超过该值时，我们可以在将其横向添加每个 n+1 块的后面，同时不会引入额外的冻结时间（下右图）：
注意到，左图中的任务所需的最短时间其实为 (n+1)×(max−1)+tot ，而右图中的最短时间就是其task序列的长度本身，若是超过了(n+1)×(max−1)+tot ，那么其所需的时间就是task的长度。
因此，我们需要返回的就是二者之中的最大值即可
代码：
class Solution {
public:
int leastInterval(vector<char>& tasks, int n) {
if(n==0)
return tasks.size();
vector<int>letterToCount(26);
for(char c:tasks){
letterToCount[c-'A']++;
}
int maxCnt=0,tot=0;
for(int i=0;i<letterToCount.size();i++){
maxCnt=std::max(maxCnt,letterToCount[i]);
}
for(int i=0;i<letterToCount.size();i++){
if(letterToCount[i]==maxCnt)
tot++;
}
int len=tasks.size();
return std::max((n+1)*(maxCnt-1)+tot,len);
}
};
- 时间复杂度：O*(n+*C)
- 空间复杂度：O©，其中 C=26 为任务字符集大小
9. 179 最大数
解法：贪心+自定义排序
对于 nums中的任意两个值 a 和 b，我们无法直接从常规角度上确定其大小/先后关系。
但我们可以根据「结果」来决定 a和 b 的排序关系：
如果拼接结果 ab 要比 ba好，那么我们会认为 a应该放在 b 前面。
例如上面的示例2中，30和3的大小比较，我们认为"3>30",原因是：330>303，即ab的拼接结果比ba好。
算法流程：
-
首先设置数组str，将nums数组转为字符串
-
然后使用自定义排序，定义排序规则为拼接后的字符串的大小比较
-
最后将数组str中的字符串转为输出的字符串
另外，注意我们需要处理前导零（最多保留一位）。即如果最后的答案的第一位是‘0’，就直接返回’0’
贪心算法的解法的正确性证明可见：179. 最大数 - 力扣（LeetCode）
代码：
class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string>str;
for(int i:nums){
str.emplace_back(to_string(i));
}
sort(str.begin(),str.end(),[](const string left,const string right){
return left+right>right+left;
});
string result="";
for(auto c:str){
result+=c;
}
if(result[0]=='0'){
return "0";
}
return result;
}
};
时间复杂度：O（n logn)
空间复杂度：O(logn)
10. 56 合并区间
解法：排序+贪心
用数组res存储最终的答案。
首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 res 数组中，并按顺序依次考虑之后的每个区间：
如果当前区间的左端点在数组res 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；
否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。
其正确性可见官方题解：
56. 合并区间 - 力扣（LeetCode）
代码：
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>>res;
if(intervals.size()==1)
return intervals;
sort(intervals.begin(),intervals.end());
res.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++){
int left=res.back()[0];
int right=res.back()[1];
if(intervals[i][0]<=right){
if(intervals[i][1]>right){
res.pop_back();
res.push_back({left,intervals[i][1]});
}
}
else{
res.push_back(intervals[i]);
}
}
return res;
}
};
时间复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的O(nlogn)。
空间复杂度：O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。
11. 57 插入区间
解法：模拟+区间合并+一次遍历
-
对于区间 $S1=[l_1,r_1] $和 S 2 = [ l 2 , r 2 ] S_2 = [l_2, r_2] S2=[l