代码随想录算法训练营第三十一天|56. 合并区间 738.单调递增的数字

题目：

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

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路：

要解决合并重叠区间的问题，可以使用贪心算法。

1. 排序区间：首先，将所有区间按照起始位置 starti 进行排序。这样可以确保在遍历区间时，每个区间的起始位置总是比前一个区间的起始位置大或相等。

2. 合并区间：创建一个空的结果数组 merged 用于存放合并后的区间。然后，依次遍历排序后的区间：

   • 如果 merged 为空或者 merged 中最后一个区间的结束位置小于当前区间的起始位置，说明当前区间与前面的区间没有重叠，可以直接将当前区间加入到 merged 中。
   • 如果 merged 中最后一个区间的结束位置大于或等于当前区间的起始位置，说明当前区间与前面的区间有重叠，此时需要将它们合并。合并的方法是更新 merged 中最后一个区间的结束位置为二者的最大结束位置。

3. 返回结果：最终，merged 中存储的就是合并后的不重叠区间。

上代码：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.empty()) return {};// 按照每个区间的起始位置排序sort(intervals.begin(), intervals.end());// 存储合并后的区间vector<vector<int>> merged;for (const auto& interval : intervals) {// 如果 merged 为空或当前区间与 merged 中最后一个区间不重叠，则将当前区间加入到 merged 中if (merged.empty() || merged.back()[1] < interval[0]) {merged.push_back(interval);} else {// 否则，合并当前区间与 merged 中最后一个区间merged.back()[1] = max(merged.back()[1], interval[1]);}}return merged;}
};

输入: n = 10
输出: 9

输入: n = 1234
输出: 1234

输入: n = 332
输出: 299

class Solution {
public:int monotoneIncreasingDigits(int n) {string digits = to_string(n);int len = digits.size();int mark = len; // 记录需要改为9的位置// 从左到右找到第一个不满足单调递增的地方for (int i = len - 1; i > 0; --i) {if (digits[i] < digits[i - 1]) {mark = i; // 从这里开始后面的都改为9digits[i - 1]--;}}// 将标记后的所有数字变为9for (int i = mark; i < len; ++i) {digits[i] = '9';}// 转换回整数并返回return stoi(digits);}
};