---

一、Leetcode 56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例：

python">以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

引用：

原文链接：https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
题目链接：https://leetcode.cn/problems/merge-intervals/description/
视频讲解：https://www.bilibili.com/video/BV1wx4y157nD/

也是重叠区间的思想，判断重叠区间的逻辑和前面差不多。

我们创建一个 result 数组，用来保存最后的结果。

首先对 intervals 数组进行排序，按照左边界从小到大排序。

然后我们将第一个区间直接放进数组中。

开始循环，循环的范围为 (1, len(intervals)) ，因为我们已经将第一个区间放入结果数组中了。

判断条件：

• 若结果数组中的最后一个区间的右边界大于等于当前区间的左边界，那么我们合并区间。具体操作就是 结果数组中的最后一个区间的右边界更新为结果数组中最后一个区间右边界和当前区间右边界的最大值。
• 反之就是不用合并区间，那么我们就把当前区间直接添加到结果数组中即可。

代码：

python">class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:if not intervals:return []intervals.sort(key=lambda x:x[0])result = []result.append(intervals[0])for i in range(1, len(intervals)):if result[-1][1] >= intervals[i][0]:result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])return result

二、Leetcode 738.单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例：

python">输入: n = 10
输出: 9

引用

原文链接：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html
题目链接：https://leetcode.cn/problems/monotone-increasing-digits/description/
视频讲解：https://www.bilibili.com/video/BV1Kv4y1x7tP/

要得到小于或等于 n 的最大单调递增数字，关键在于从右往左检查数字的每一位，一旦发现某一位数字比它右边相邻的数字大，就需要对该位数字进行调整，同时为保证得到的结果是最大的，要将调整位之后的所有数字都设为 9。

将输入的整数 n 转换为字符串，再把字符串转换为字符列表 strNum，方便我们后续操作。

使用一个循环从右往左遍历字符列表 strNum。从右往左遍历的原因是，当发现某一位数字不符合单调递增的条件时，需要对该位及其右边的数字进行调整，从右往左遍历能保证我们优先处理低位数字，避免高位数字调整后对低位数字产生影响。

在遍历过程中，针对每一位数字，检查它是否比其右边相邻的数字大。若大，就表明当前数字序列并非单调递增，需要进行调整。调整的方式是把该位数字减 1，这是为了保证调整后的数字小于原数字。

将调整位之后的所有数字都设为 9。这是因为在调整某一位数字后，为了得到小于或等于 n 的最大单调递增数字，需要让调整位之后的数字尽可能大，而每一位最大的数字就是 9。

代码：

python">class Solution:def monotoneIncreasingDigits(self, n: int) -> int:# 将整数转换为字符串strNum = list(str(n))# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小，说明需要修改前一个字符if strNum[i - 1] > strNum[i]:strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质for j in range(i, len(strNum)):strNum[j] = '9'# 将列表转换为字符串，并将字符串转换为整数并返回return int(''.join(strNum))