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

【chap10-贪心算法】用Python3刷《代码随想录》

news 2026/8/21 19:32:22

1、什么是贪心：本质是找到每个阶段的局部最优，从而去推导全局最优

如取钞票的例子：

而背包问题要用动态规划的思路解决，不能用贪心算法

2、贪心的套路

无方法论
如何通过局部最优推导出全局最优？若找不出明显的反例，就可以试试
没必要通过严格的数学证明（数学归纳法/反证法）来推导贪心的合理性

题目分类

455. 分发饼干

全局最优是喂饱尽可能多的孩子。有两种思路

（1）优先使用大饼干：尽量用大饼干去喂胃口大的孩子

要先对两个数组排序（从小到大）
遍历孩子数组时要从大到小，即从后往前（外面的for循环控制，下标i是固定移动的）
饼干数组由if里面的下标index控制，符合条件才移动

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: # g是孩子，s是饼干 g.sort() s.sort() index = len(s)-1 # 饼干序列的下标 kid_cnt = 0 # 满足孩子的计数 for i in range(len(g)-1, -1, -1): if index >= 0 and g[i] <= s[index]: # 注意要加index>=0，且放在前面 kid_cnt += 1 # 成功投喂了一个孩子 index -= 1 # 饼干被成功投喂后才向前一位 return kid_cnt

时间复杂度：O(nlogn)【Python中的sort()方法的时间复杂度是O(nlogn)】
空间复杂度：O(1)

使用一个index自减的方式来控制饼干数组的遍历，而不是又使用一层for循环去遍历，这也是常用的技巧

（2）优先使用小饼干：尺寸小的饼干先喂饱胃口小的孩子

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: # g是孩子，s是饼干 g.sort() s.sort() index = 0 res = 0 for i in range(len(s)): if index < len(g) and s[i] >= g[index]: res += 1 index += 1 return res

2410. 运动员和训练师的最大匹配数

饼干类比trainers（训练师），孩子类比players（运动员）

优先匹配大

class Solution: def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int: players.sort() trainers.sort() res = 0 index = len(trainers)-1 for i in range(len(players)-1, -1, -1): if index >= 0 and players[i] <= trainers[index]: index -= 1 res += 1 return res

优先匹配小

class Solution: def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int: players.sort() trainers.sort() res = 0 # 最大匹配数 index = 0 for i in range(len(trainers)): if index < len(players) and players[index] <= trainers[i]: res += 1 index += 1 return res

53. 最大子数组和

起始位置：当连续和为负数的时候（注意不是遇到负数就~），就选择下一个数作为新的起点，重新计算连续和
终止位置：最大的result（区间和）的位置

下面的例子中，三段区间的和分别为1、6、4，所以最终的最大子数组和为6

class Solution: def maxSubArray(self, nums: List[int]) -> int: sub_sum = 0 res = float("-inf") for i in range(len(nums)): sub_sum += nums[i] res = max(res, sub_sum) # 取区间累计的最大值（相当于不断确定最大子序列的终止位置） # 相当于重置最大子序列的起始位置，因为遇到负数一定降低了总和 if sub_sum < 0: sub_sum = 0 return res

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

1005. K次取反后最大化的数组和

K次取反要用完。两次贪心：

第一次贪心：优先对负数进行取反，负数里优先对绝对值最大的负数进行取反
第二次贪心：如果负数全部取反之后K还没用完，优先对数组里的最小值反复取反，把K全部消耗掉，即使最小的非负整数最后变为负数，影响也是最小的

代码：

第一次贪心：
- 对数组进行排序，自定义比较函数，按绝对值的大小（从大到小）进行排序
第二次贪心：
- 如果剩下的k是奇数的话，就对此时列表中的最后一个数（最小的非负整数）取反k次
- 如果剩下的k是偶数，取反k次没有影响
- 注意这里没必要while循环，这样写性能较差
最后将数组中的数累加起来即可

class Solution: def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: # 按绝对值从大到小排序 # 如 [3,-1,0,2] -> [3,2,-1,0] nums.sort(key=lambda x: abs(x), reverse=True) # 先对最大的负数取反 for i in range(len(nums)): if k > 0 and nums[i] < 0: nums[i] *= -1 k -= 1 # 再对最小的非负整数反复取反，直至k被消耗完 if k % 2 != 0: nums[len(nums)-1] *= -1 # 最后返回数组和 return sum(nums)

list.sort()是 Python 中用于对列表进行原地排序的方法。用法如下：
list.sort(key=None, reverse=False)
key：指定排序规则的函数（可选）
reverse：是否降序（从大到小）排序，默认为False（升序，从小到大）

134. 加油站

题目：

环路。如果可以绕环路行驶一周，则返回出发时加油站的编号（如果题目有解则答案唯一），否则返回-1
汽车油箱容量无限，从其中一个加油站出发，出发时油箱为空

暴力法

遍历每一个加油站为起点的情况，模拟汽车行驶一圈的过程，如果汽车行驶了一圈，中途没有断油，且最后油量 ≥ 0，说明这个起点是满足题目要求的

for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: for i in range(len(gas)): rest = gas[i] - cost[i] # 记录剩余油量 index = (i+1) % len(gas) # 下一个加油站的索引 # 模拟以i为起点，汽车行驶一圈的过程 while rest > 0 and index != i: rest += gas[index] - cost[index] # 更新剩余油量 index = (index + 1) % len(gas) # 更新下一个加油站的索引 # 如果以i为起点汽车行驶一圈，剩余油量≥0，则返回该起始位置 if rest >= 0 and index == i: return i return -1

时间复杂度：O(n^2）
空间复杂度：O(n）
暴力法会超时，只能过36/40个用例

贪心法

curSum变量累加每一个站点剩余的油量，一旦剩余的油量变为负数了，就选择下一个站点作为新的起始位置，再从0开始计算curSum

反证法：

局部最优：当前 rest[j] 累加的和 curSum 一旦小于0，则起始位置至少是 j+1
全局最优：找到汽车可以行驶一圈的起始位置

如果总油量 - 总消耗 ≥ 0，那么汽车一定可以行驶完一圈，说明各个站点的加油站的剩油量 rest[i] = gas[i] - cost[i] 相加后一定 ≥ 0

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: cur_sum = 0 # 每一站剩余的油量 total_sum = 0 # 所有剩余的油量全部加在一起 start = 0 for i in range(len(gas)): cur_sum += gas[i] - cost[i] total_sum += gas[i] - cost[i] # 若当前累加rest[i]和小于0，从新的位置再去统计当前剩余的油量 if cur_sum < 0: start = i+1 # 起始位置更新为i+1 cur_sum = 0 # curSum从0开始计算 # 说明怎么走都不可能行驶一圈 if total_sum < 0: return -1 return start

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

860. 柠檬水找零

账单是20的情况，为什么要优先消耗一个10和一个5呢？

因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能
所以局部最优：遇到账单20，优先消耗10来完成本次找零

class Solution: def lemonadeChange(self, bills: List[int]) -> bool: five, ten, twenty = 0, 0, 0 for i in bills: if i == 5: five += 1 elif i == 10: if five <= 0: return False ten += 1 five -= 1 elif i == 20: # 优先消耗10美元，因为5美元的找零用处更大，能多留就多留 if ten > 0 and five > 0: twenty += 1 # 其实这一行代码可以删除，因为记录20已经没有意义了，不会用20来找零 ten -= 1 five -= 1 elif five >= 3: twenty += 1 # 同理，这行代码也可以删除 five -= 3 else: return False return True

968. 监控二叉树

一个摄像头可以覆盖上中下三个覆盖范围

对于叶子节点，尽量在叶子节点的父节点放摄像头
然后一层一层往上推，每隔两个空节点放一个摄像头，直到遍历到根节点
为什么不看根节点？即遇到根节点，在根节点的孩子处放一个摄像头。因为二叉树中叶子节点数量相比根节点数量，呈指数级增长，因此要优先在叶子节点上节约摄像头
因为要从下往上遍历二叉树，所以一定是后序遍历

（1）如何控制每隔两个节点放一个摄像头？

记录每个节点的状态，根据左右孩子的状态去确定父节点的状态，根据状态再决定节点是否应该放摄像头
每个节点的状态有：
- 0：无覆盖
- 1：有摄像头
- 2：有覆盖
- 注：无摄像头的状态即0和2

（2）遍历到空节点时，空节点应该是什么状态呢？【有覆盖的状态】

不能是有摄像头的状态。否则叶子节点就是被覆盖了，没必要再在叶子节点的父节点放摄像头
不能是无覆盖的状态。否则传到其父节点，即叶子节点时，叶子节点一定要放摄像头

（3）如何做状态转移？从底往上遍历只有以下三种情况：

左右孩子都有覆盖：父节点只能是状态0，等着父节点的父节点有摄像头将其覆盖
左右孩子至少有一个是无覆盖：父节点一定要装摄像头才能将其覆盖
左右孩子至少有一个有摄像头：父节点一定是有覆盖的状态
第四种补充情况：如果遍历完了，根节点还是无覆盖状态，那么还要给根节点加一个摄像头。如下图：

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def minCameraCover(self, root: Optional[TreeNode]) -> int: self.res = 0 # 对要放摄像头的情况进行计数 # 情况4: 若最后根节点是无覆盖的状态，还需要加一个摄像头 if self.traversal(root) == 0: self.res += 1 return self.res # 从底往上遍历二叉树，返回的是状态 # 定义状态如下： # 0: 该节点未覆盖 # 1: 该节点有摄像头 # 2: 该节点有覆盖 def traversal(self, cur): # 终止条件 if not cur: # 遇到空节点时就要往上返回 return 2 # 2表示有覆盖 # 左，left接收的是左孩子的状态 left = self.traversal(cur.left) # 右 right = self.traversal(cur.right) # 中，根据左右孩子的状态判断父节点的状态 # 情况1: 左右节点都有覆盖 if left == 2 and right == 2: return 0 # 0表示无覆盖 # 情况2: 左右孩子至少有一个是无覆盖 if left == 0 or right == 0: self.res += 1 return 1 # 1表示要放摄像头 # 情况3: 左右孩子至少有一个有摄像头 if left == 1 or right == 1: return 2 # 2表示有覆盖

序列问题

376. 摆动序列【难】

代码随想录的分析

https://programmercarl.com/0376.摆动序列.html#算法公开课

1、题目：给一个数组，可以在数组里删除元素，求问删除元素之后数组里最长的摆动序列是多少

摆动序列定义：相邻元素的差值要保证一正一负。数组的两端默认有两个摆动（两端数值不相同的情况下）
- 如 [2, 2] 有一个摆动，[2, 3] 有两个摆动
- 题目中说了：仅有一个元素或者含两个不等元素的序列也视作摆动序列

if len(nums) == 1: return 1 if len(nums) == 2: if nums[0] == nums[1]: return 1 else: return 2

数组里有可能相邻元素的数值相同，即有平坡。若有个平坡再上去或下去，不算摆动，此时需要删除元素
- 如 [1, 2, 2, 2, 1]，最长摆动序列为3，删除前两个2即可，即[1, 2, 1]
- 更长的一个例子：

2、思路：其实下面的条件中 prediff 是可以带等号的，后面会详细解释

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），这个坡度就可以有两个局部峰值（一个峰谷一个峰底），每个局部峰值都是一个摆动
全局最优：整个序列有最多的局部峰值，从而获得最长的摆动序列
在实际操作中，其实连删除的操作都不用做，因为要求的是最长摆动子序列的长度，只需要统计数组的峰值数量就可以了。相当于删除单调坡度上的节点，然后统计长度

3、三种特殊情况：

上下有平坡：允许preDiff=0

首尾元素：至少要有3个元素才能计算 preDiff 和 curDiff。如果只有2个元素，可以在最前面造一个平坡（preDiff 初始化为 0 即可）

单调有平坡：preDiff 只记录当摆动出现的时候，下一个坡的初始坡度；然后 preDiff 就不用改变了（平坡保持不变）；直到遇到下一个摆动的时候，坡的方向改变，preDiff 再继续改变

4、代码：

class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: # 特殊情况处理，也可省略 if len(nums) == 1: return 1 if len(nums) == 2: if nums[0] == nums[1]: return 1 else: return 2 cur_diff, pre_diff = 0, 0 # pre_diff初始化为0，就是默认前面延长了一段平坡 res = 1 # 默认序列最右边就是有一个摆动，所以初始化为1 for i in range(len(nums)-1): # 最后一个元素不需要遍历了，因为默认有个摆动 cur_diff = nums[i+1] - nums[i] if (cur_diff > 0 and pre_diff <= 0) or (cur_diff < 0 and pre_diff >= 0): # 出现摆动 res += 1 pre_diff = cur_diff # 放在if判断里，为了处理单调有平坡的情况（坡度方向变化时pre_diff才改变，平坡不改变） return res

时间复杂度：O(n)，只需遍历一次数组
空间复杂度：O(1)，只用几个额外变量

个人感觉更易理解的分析

不需要真的找出子序列，只需要统计方向变化的次数（从上升变下降，或从下降变上升），每变化一次就多一个元素，答案就是变化次数+1

从左到右扫描每对相邻元素，每次遇到方向变化，count就+1
如果方向没变，说明是单调的一段，直接跳过
这就是贪心的精髓，只保留拐点，忽略中间的单调部分
扫描完成时，count就是最长摆动子序列的长度，整个过程只需要一次遍历

class Solution: def wiggleMaxLength(self, nums: List[int]) -> int: pre_diff = 0 # 记录上一次的差值方向 count = 1 # 记录摆动序列长度 for i in range(1, len(nums)): diff = nums[i] - nums[i-1] # 计算相邻元素的差值diff # 如果diff>0且之前方向非正，说明出现了上升拐点 # 如果diff<0且之前方向非负，说明出现了下降拐点 if (diff > 0 and pre_diff <=0) or (diff < 0 and pre_diff >= 0): count += 1 # 出现拐点就count+1 pre_diff = diff # 同时更新pre_diff return count # 最终返回count就是最长摆动子序列的长度

贪心核心：不需要关心具体是哪些元素，只需要统计峰谷交替的次数，方向每变化一次，count就+1

738. 单调递增的数字

题目：求 ≤ N 的最大单调递增的整数

局部最优：遇到 strNum[i-1] > strNum[i] 的情况，首先将 strNum[i-1] 减1，然后将 strNum[i] 赋值为9，可以将这两个数变成最大单调递增的整数

从后往前遍历，才能利用上一次比较的结果

class Solution: def monotoneIncreasingDigits(self, n: int) -> int: str_num = str(n) # 为了方便遍历，把输入的int类型转为str类型 flag = len(str_num) # 用来标记从哪里开始后面都赋值为9 # 从后往前遍历 # 注意i结束的下标是1，因为有i-1，若结束的下标为0则索引变为负数 for i in range(len(str_num)-1, 0, -1): if str_num[i-1] > str_num[i]: # 前一位 > 后一位时 # 前一位减1 str_num = str_num[:i-1] + str(int(str_num[i-1])-1) + str_num[i:] # 后一位变为9 flag = i # 从i开始往后都变为9 for i in range(flag, len(str_num)): # 第一个9后面一定全是9 str_num = str_num[:i] + '9' + str_num[i+1:] return int(str_num) # str -> int

flag 的作用是什么？

标记从哪一位开始统一改成9，即 flag 往后都要为9
如1000，1>0，故1变为0，第二位的0变为9，后面的两个0也要变为9，即0999

为什么 flag 初始化为 len(str_num)？

为了防止在 flag 没有被赋值的情况下执行第二个for循环
如1234，本身就是符合条件的，直接输出即可。第一个for循环不会执行，flag没有被赋值；初始化为 len(str_num) 时，第二个for循环也会被跳过

贪心解决股票问题

122. 买卖股票的最佳时机II

想获得利润至少以两天为一个交易单元，因此第一天没有利润，利润序列比股票序列少一天
最终利润是可以分解成以天为单位的维度
只需要收集每天的正利润即可（局部最优），收集的正利润的区间就是股票买卖的区间，这样最后得到的就是最大利润了（全局最优）

class Solution: def maxProfit(self, prices: List[int]) -> int: res = 0 for i in range(1, len(prices)): # 至少要从下标1的位置才能减去昨天的价格，才能得到当天的利润 profit = prices[i] - prices[i-1] if profit > 0: res += profit return res

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

714. 买卖股票的最佳时机含手续费

122题是没有手续费的情况，它的逻辑是：只要今天比昨天价格高，就累加差价（相当于每天都在买卖，无限次交易）；

而本题有手续费fee，不能简单累加所有正差价，因为每次交易（买入 + 卖出）要付一次手续费，所以需要合并连续上涨的区间，只在一次交易的末尾扣除一次手续费

class Solution: def maxProfit(self, prices: List[int], fee: int) -> int: buy = prices[0] # 第一次买入的价格 res = 0 for i in range(1, len(prices)): # 如果当前价格比买入价还低，说明买入成本可以降低 if prices[i] < buy: buy = prices[i] # 如果当前价格 > buy + fee，说明可以卖出获利 if prices[i] - fee - buy > 0: res += prices[i] - fee - buy # 赚取差价，扣除手续费 # 关键：卖出后，如果价格继续涨，相当于在卖出的位置重新买入（不重复扣手续费） buy = prices[i] - fee # 避免重复扣手续费 return res

区间问题

55. 跳跃游戏

不用纠结具体跳几步，重点看跳跃的覆盖范围能否cover到终点

每次都取一个最大的覆盖范围
在已有的覆盖范围内遍历每个元素，得到了新的可跳跃步数，去更新覆盖范围

class Solution: def canJump(self, nums: List[int]) -> bool: # 只有一个元素，直接返回True，说明可以到终点 if len(nums) == 1: return True cover = 0 for i in range(len(nums)): if i <= cover: # i每次只能在cover的范围内移动 # 每移动一个元素，cover就可以扩大覆盖范围，让i继续移动下去 cover = max(cover, i+nums[i]) # cover每次只取覆盖的最大值 # 如果cover >= 终点的下标，就说明可以到达最后位置 if cover >= len(nums)-1: return True return False

45. 跳跃游戏II

误区：每一步尽量往远跳，只要跳到终点了，用的就是最少的跳跃次数

正确思路：每跳一步尽可能地去增加覆盖范围，用最少的步数去增加最大的覆盖范围，一旦覆盖范围覆盖到了终点，输出步数即可，就是最小步数

局部最优：在当前可移动距离固定的情况下尽可能多走，如果还没到达终点，则步数再+1
全局最优：用最小步数到达终点

需要统计两个覆盖范围：当前这一步的最大覆盖范围、下一步的最大覆盖范围

如果移动下标到达了当前这一步覆盖的最远距离，却还没有到达终点，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点

class Solution: def jump(self, nums: List[int]) -> int: if len(nums) == 1: # 起点就是终点，不用走 return 0 cur_dis, next_dis = 0, 0 # 当前以及下一步覆盖的最远距离的下标 step = 0 # 已经走的步数 for i in range(len(nums)): next_dis = max(next_dis, i+nums[i]) # 只记录下一步能覆盖的最远距离 if i == cur_dis: # i走到当前覆盖范围的终点 if i != len(nums)-1: # 但没走到数组的终点 step += 1 # 需要走下一步 cur_dis = next_dis # 更新当前覆盖范围的下标 if next_dis >= len(nums)-1: # 若下一步的覆盖范围已经包含终点 break else: # 当前覆盖的最远距离的下标是集合终点 break return step

452. 用最少数量的箭引爆气球

局部最优：当气球出现重叠时，一起射，所使用的弓箭最少

如何模拟气球被射爆的过程呢？

如果真实地模拟射气球的过程，那么应该射爆一个气球，气球数组就删除一个元素
但：如果把气球排序之后，从前到后遍历气球，跳过被射过的气球即可。没必要让气球数组删除一个元素，只要记录弓箭的数量即可

为了让气球尽可能重叠，对气球进行排序，让相邻的气球挨在一起。按左边界or右边界排序都可以，只不过对应的遍历顺序不同

下面的逻辑是按左边界排序进行的：

既然按照起始位置排序，就要从前往后遍历气球数组，尽可能让气球重复
若 i 气球的左边界 > 其前一个气球的右边界，说明两个气球不重叠，此时一定需要一个额外的弓箭
若 i 气球的左边界 ≤ 其前一个气球的右边界，说明两个气球重叠，此时还需再看看和下一个气球是否也重叠（是否能一箭三雕）。取 i 气球和 i-1 气球的最小右边界，来更新 i 气球的右边界，从而跟下一个气球的左边界进行比较

class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: points.sort(key=lambda x: x[0]) # 气球按左边界进行排序 res = 1 # points不为空，至少需要一支弓箭 for i in range(1, len(points)): # i气球的左边界 > 前一个气球的右边界 if points[i][0] > points[i-1][1]: res += 1 # 需要一支弓箭 # 气球i和i-1挨着 else: points[i][1] = min(points[i][1], points[i-1][1]) # 更新当前气球的右边界 return res

时间复杂度：O(nlogn)，来自于排序
空间复杂度：O(n)，Python的 Timsort 排序需要O(n)的额外空间（用于合并操作）

435. 无重叠区间

等价于求重叠区间的数量

对数组按左边界进行排序
若 i 区间的左边界 ≥ 上一个区间的右边界，说明这两个区间不重叠，没有任何处理逻辑；

否则，这两个区间就重叠，记录重叠个数；同时取这两个重叠区间右边界的min，和下一个区间的左边界进行判断，判断下一个区间是否继续重叠

class Solution: def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda x:x[0]) res = 0 for i in range(1, len(intervals)): if intervals[i][0] < intervals[i-1][1]: res += 1 intervals[i][1] = min(intervals[i-1][1], intervals[i][1]) return res

763. 划分字母区间

字母的最远出现位置就是一个分界线

定义哈希数组来记录每一个字母最远出现的位置（遍历一遍数组即可）
遍历字符串，right为区间可能包含字母的最远下标位置
当遍历到了最远下标位置时，就寻找到了分割点，该区间包含的所有字符都只出现在这个区间里，记录区间长度，同时更新下一个区间的起始位置left

class Solution: def partitionLabels(self, s: str) -> List[int]: # 统计每一个字符最后出现的位置 far_idx = [0]*26 for i in range(len(s)): far_idx[ord(s[i]) - ord('a')] = i left, right = 0, 0 res = [] for i in range(len(s)): # 找到字符出现的最远边界 right = max(right, far_idx[ord(s[i]) - ord('a')]) # 如果字符最远出现位置下标和当前下标相等，则找到了分割点 if i == right: res.append(right-left+1) # 记录区间长度 left = i+1 # 更新区间左边界 return res

时间复杂度：O(n)
空间复杂度：O(1)，使用的hash数组是固定大小，因为s仅由小写英文字母组成

56. 合并区间

本题在判断两个区间重叠之后，再加一个合并的操作

按照左边界排序，排序之后，局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了

按照左边界从小到大排序之后，如果 intervals[i] 的左边界 <= intervals[i-1] 的右边界，则一定有重叠（本题相邻区间也算重叠，所以是<=）
用合并区间后左边界和右边界，作为一个新的区间，加入到result数组；如果没有合并就把原区间加入到result数组

以下写法可以不用重复地添加res数组，合并后的区间直接就更新到res数组里了：

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: res = [] intervals.sort(key=lambda x:x[0]) # 先把第一个区间加到最后结果里 res.append(intervals[0]) for i in range(1, len(intervals)): # 若当前遍历区间的左边界 ≤ 上一个区间的右边界 if intervals[i][0] <= res[-1][1]: # 上一个区间的左边界一定是最小的 # 要更新的是右边界，取较大的那个 res[-1][1] = max(res[-1][1], intervals[i][1]) else: # 没重叠 # 直接把当前遍历的区间放进res数组即可 res.append(intervals[i]) return res

时间复杂度：O(nlogn)
空间复杂度：O(n)

两个维度权衡问题

两个维度同时需要考虑的问题，一定不要两边兼顾，会顾此失彼。应该先确定一个维度之后再确定另一个维度

135. 分发糖果

题目：

每个孩子至少得到1颗糖果
相邻的孩子中评分高的孩子必须获得更多糖果
问老师最少要准备多少颗糖果

思路：

（1）先确定右边孩子比左边孩子得分高的情况（从前往后遍历）

局部最优：只要右边孩子的评分比左边的高，那么右边孩子就多得到一颗糖果

（2）再确定左边孩子比右边孩子得分高的情况（从后往前遍历）

一定要从后往前遍历，从前往后遍历不可以。如果从前往后遍历，根据 ratings[i+1] 来确定 ratings[i] 对应的糖果，就不能利用上一次的比较结果了

如果 ratings[i] > ratings[i+1]，此时 candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是 candyVec[i+1] + 1（从右边这个加1得到的糖果数量），一个是 candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）
那么又要贪心了，局部最优：取 candyVec[i+1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的

class Solution: def candy(self, ratings: List[int]) -> int: candy_num = [1] * len(ratings) # 默认初始值为1，因为每个孩子至少要有一个糖果 # 先确定右边孩子比左边孩子得分高的情况（从前往后遍历） for i in range(1, len(ratings)): if ratings[i] > ratings[i-1]: candy_num[i] = candy_num[i-1] + 1 # 再确定左边孩子比右边孩子得分高的情况（从后往前遍历） for i in range(len(ratings)-2, -1, -1): if ratings[i] > ratings[i+1]: candy_num[i] = max(candy_num[i], candy_num[i+1]+1) # 统计结果 return sum(candy_num)

本题需要采用两次贪心的策略：
一次是从左到右遍历，只比较右边孩子的评分比左边大的情况
另一次是从右到左遍历，只比较左边孩子的评分比右边大的情况

406. 根据身高重建队列

[h, k]，h表示身高，k表示前面有k个人的身高是 ≥h 的。按照这个要求重新排列

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

（1）k维度，按k从小到大排序

当k相同时，就按h从小到大排序

[[5,0],[7,0],[6,1],[7,1],[5,2],[4,4]]

（2）h维度，按h从大到小排序，这样每一个人前面一定比他高

当h相同时，就按k从小到大排序
再按照k去调整，插入到对应的位置，让队列再满足k的属性

注意要新定义一个队列，而不是在原输入队列中直接插入。在原队列直接插入的话元素位置已经被改变，在遍历时很可能重复去访问同一个元素

class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: # 先按身高降序排序，身高相同按k值升序排序 people.sort(key=lambda x: (-x[0], x[1])) queue = [] for i in range(len(people)): pos = people[i][1] # 直接在k索引位置插入 queue.insert(pos, people[i]) return queue

在Python中，可以通过list.insert(index, element)在列表的指定位置插入元素
insert时间复杂度O(n)，需要移动插入位置后的所有元素
若插入位置的index超出长度，则插在末尾；超出负范围，则插在开头
insert方法直接修改原列表