【LeetCode 刷题】贪心算法(4)-区间问题

此博客为《代码随想录》贪心算法章节的学习笔记，主要内容为贪心算法区间问题的相关题目解析。

55. 跳跃游戏

题目链接

class Solution:def canJump(self, nums: List[int]) -> bool:mx = 0  # 最右可达位置for i, jump in enumerate(nums):if i > mx:return Falsemx = max(mx, i + jump)if mx >= len(nums) - 1:return True

• 维护当前可达的最大右边界，当前下标位置不可达时，返回 False；mx 已经 >= 最后一个元素的下标时，提前返回 True
• 也可理解为区间合并问题，将每一个元素对应为 [i, i + jump] 的区间，求是否能够合并出右边界 >= 最后一个元素下标的大区间

45. 跳跃游戏 II

题目链接

class Solution:def jump(self, nums: List[int]) -> int:res = 0cur_rigth, next_right = 0, 0for i in range(len(nums) - 1):next_right = max(next_right, i + nums[i])if i == cur_rigth:cur_rigth = next_rightres += 1return res

• 要求最小跳跃次数，因此不能每走一步都合并区间，而是应该走到当前步所能达到的尽头，再尝试进行一次跳跃；再当前步走的过程中，同时维护下一次跳跃所能到达的最远边界
• 由于题目的测试用例均能够到达终点，因此无需特判无法到达的逻辑

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

题目链接

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key=lambda x: x[1])res = 0cur = -inffor start, end in points:if start > cur:cur = endres += 1return res

• 按照区间右边界升序排列，每次射出的箭都处于当前区间的右边界，以尽可能多的同时覆盖其他区间
• 一旦当前区间的右边界无法覆盖后续某个区间，则需要新的一支箭，同时射箭的位置调整为新区间的右边界

435. 无重叠区间

题目链接

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x : x[1])res = 0cur_right = -inffor start, end in intervals:if start >= cur_right:res += 1cur_right = endreturn len(intervals) - res

• 移除最少 等价于 保留最多
• 同样按照区间右边界升序排列，如果当前区间的起点和之前的区间没有重叠（当前区间起点 >= 之前区间最大右边界），即保留当前区间

763. 划分字母区间

题目链接

class Solution:def partitionLabels(self, s: str) -> List[int]:dic = {}for idx, c in enumerate(s):dic[c] = idxcur_left, cur_right = 0, -infres = []for idx, c in enumerate(s):cur_right = max(cur_right, dic[c])if cur_right == idx:res.append(cur_right - cur_left + 1)cur_left = cur_right + 1cur_right = -infreturn res

• 先统计每个字母出现的最后位置，之后按顺序遍历，如果当前所有出现过的字母的最后出现位置的最大值 == idx，则表示可以划分为一个合法区间

56. 合并区间

题目链接

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[0])res = []for start, end in intervals:if res and start <= res[-1][1]:res[-1][1] = max(res[-1][1], end)else:res.append([start, end])return res

• 按照区间左边界升序排列：因为题目要求返回合并后的区间，按照左边界排序后，如果发生区间合并，也无需修改合并区间左边界的值
• res[-1] 保存着当前正在合并处理的区间
• 此题与 “452. 用最少数量的箭引爆气球” 和 “435.无重叠区间” 不是相同的解题思路