代码随想录-Day37

56. 合并区间

以数组 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] 可被视为重叠区间。
在这里插入图片描述

方法一：

/**
时间复杂度 ： O(NlogN) 排序需要O(NlogN)
空间复杂度 ： O(logN)  java 的内置排序是快速排序 需要 O(logN)空间

*/
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
        //initial start 是最小左边界
        int start = intervals[0][0];
        int rightmostRightBound = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            //如果左边界大于最大右边界
            if (intervals[i][0] > rightmostRightBound) {
                //加入区间 并且更新start
                res.add(new int[]{start, rightmostRightBound});
                start = intervals[i][0];
                rightmostRightBound = intervals[i][1];
            } else {
                //更新最大右边界
                rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
            }
        }
        res.add(new int[]{start, rightmostRightBound});
        return res.toArray(new int[res.size()][]);
    }
}

这段Java代码实现了一个函数 merge，用于合并一系列有重叠的区间。给定一个二维数组 intervals，其中每个 intervals[i] 是一个长度为2的数组，表示一个区间 [start, end]，该函数的目标是将这些区间合并成一个新的区间数组，使得在新数组中任意两个区间没有交集，并且覆盖所有原始区间。以下是代码的详细解析：

时间复杂度和空间复杂度说明

时间复杂度：O(NlogN)，主要来自对区间按左边界排序的操作，其中N是区间数量。
空间复杂度：O(logN)，这是由于Java内置排序方法（快速排序）的递归调用栈空间。

代码解析

初始化：创建一个名为 res 的 LinkedList 用于存储不重叠的合并后的区间。同时，初始化 start 为数组中第一个区间的起始位置，rightmostRightBound 为当前已知的最远的右边界。
排序：使用 Arrays.sort() 方法按区间的左边界升序排序整个 intervals 数组。排序是本算法的关键步骤，它确保了后续遍历过程中的合并逻辑简单且有效。
遍历并合并：
- 遍历排序后的区间数组。对于每个区间，如果当前区间的起始位置大于已知的最远右边界，说明当前区间与之前处理过的所有区间都不重叠，可以将前一个区间的结束位置与 start 组成的区间加入结果列表 res，并更新 start 为当前区间的起始位置，同时更新 rightmostRightBound 为当前区间的结束位置。
- 如果当前区间起始位置不大于最远右边界，说明当前区间与前一个区间有重叠，此时只需要更新 rightmostRightBound 为当前区间和已知最远右边界中的较大值，以覆盖更大的范围。
添加最后一个区间：遍历结束后，别忘了将最后一个有效区间 [start, rightmostRightBound] 添加到结果列表 res 中。
转换并返回结果：最后，将 res 中的数据转换成数组类型并返回。

示例说明

假设输入区间为 [[1,3],[2,6],[8,10],[15,18]]，经过排序、遍历合并后，最终的不重叠区间数组将是 [[1,6],[8,10],[15,18]]，这正是函数预期输出的结果。

// 版本2
class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.getLast()[1]) {
                int start = res.getLast()[0];
                int end = Math.max(intervals[i][1], res.getLast()[1]);
                res.removeLast();
                res.add(new int[]{start, end});
            }
            else {
                res.add(intervals[i]);
            }         
        }
        return res.toArray(new int[res.size()][]);
    }
}

这个Java代码是用于解决“合并区间”问题的另一个版本实现。给定一个二维数组 intervals，其中每个 intervals[i] 为一个长度为2的数组，表示一个区间 [start, end]，该函数的目标是将所有重叠的区间合并成一个新的区间数组，并且在新数组中任意两个区间不会有重叠部分。下面是该代码的详细解析：

代码解析

初始化：定义一个 LinkedList<int[]> res 作为结果容器来存储合并后的区间。使用 Arrays.sort() 方法对输入区间按起始位置升序排序，便于后续处理。
添加首个区间：将排序后的首个区间直接加入结果列表 res。
遍历合并：从第二个区间开始遍历整个 intervals 数组。对于每个区间，执行以下操作：
- 判断重叠：如果当前区间的起始位置 intervals[i][0] 小于等于结果列表中最后一个区间的结束位置 res.getLast()[1]，说明这两个区间有重叠。
- 合并区间：当发现重叠时，合并这两个区间。新的起始位置取两者中较小的（在这里直接取了 res.getLast()[0]，因为当前区间起始位置肯定不会小于已加入的区间的起始位置），新的结束位置取两者结束位置的较大值。然后从 res 中移除旧的最后一个区间，添加合并后的新区间。
- 无重叠则直接添加：如果当前区间与结果列表最后一个区间无重叠，则直接将当前区间加入到结果列表 res 中。
转换并返回结果：遍历结束后，将 LinkedList 类型的结果列表转换为数组类型并返回。

时间复杂度和空间复杂度

时间复杂度：O(NlogN)，其中N为区间数量。排序操作占主导地位。
空间复杂度：O(N)，res 用于存储不重叠的合并区间，最坏情况下需要与输入区间相同的空间。

示例说明

例如，给定输入区间 [[1,3],[2,6],[8,10],[15,18]]，经过处理后，合并后的区间应为 [[1,6],[8,10],[15,18]]，这正是该函数预期返回的结果。

738. 单调递增的数字

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

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

示例 1:

输入: n = 10
输出: 9
示例 2:

输入: n = 1234
输出: 1234
示例 3:

输入: n = 332
输出: 299

方法一：

版本1
class Solution {
    public int monotoneIncreasingDigits(int N) {
        String[] strings = (N + "").split("");
        int start = strings.length;
        for (int i = strings.length - 1; i > 0; i--) {
            if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
        for (int i = start; i < strings.length; i++) {
            strings[i] = "9";
        }
        return Integer.parseInt(String.join("",strings));
    }
}

这段Java代码是为了解决一个问题：给定一个非负整数N，找到具有单调递增数字的最大的数，其数字重新排列后小于或等于N。单调递增数字是指每个位置上的数字都不小于其左侧的数字（从左到右）。

代码解析

字符串转换：首先，将整数N转换成字符串数组strings，方便单独处理每一位数字。
从右向左扫描：使用一个外层循环从字符串的末尾开始向前遍历（索引i从strings.length - 1到0），目的是检测数字是否递减。如果当前位的数字小于前一位的数字（strings[i] < strings[i - 1]），则：
- 将前一位的数字减一（(Integer.parseInt(strings[i - 1]) - 1)），并将其转换回字符串形式。
- 记录这个位置start = i，作为后续处理的起点，因为start右侧的所有数字都需要变成9以确保结果是最大的单调递增数字。
填充9：使用一个内层循环，从位置start到字符串的末尾，将所有这些位置的数字替换为"9"，以确保生成的数字尽可能大。
转换回整数并返回：最后，使用String.join("", strings)将修改后的字符串数组连接成一个字符串，再通过Integer.parseInt(...)将其转换回整数并返回。

示例

例如，如果N = 332，经过处理后的字符串数组变为["3", "2", "9"]，重新组合并转换回整数得到329，这是小于等于332的最大单调递增数字。

注意：这个解法在处理边界情况（如当N本身就是单调递增或需要大幅度减少首位数字时）表现良好，但在某些情况下可能不是最高效的算法，特别是在N非常大，且大部分数字都需要减少时。

方法二：

版本2
class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

这个版本的代码实现与第一个版本非常相似，主要的不同在于细节处理和变量命名上，逻辑本质上是一致的。下面是这个版本的解析：

代码解析

转换为字符数组：首先，将整数n转换为字符串s，然后进一步转换成字符数组chars。这样可以直接操作每一位数字，无需频繁地在数字和字符串之间转换。
从右向左扫描：外层循环的起始点调整为i = s.length() - 2，这是因为现在是从倒数第二位开始比较（避免数组越界，同时正确定位需要检查的相邻数字对）。如果发现chars[i]大于chars[i + 1]，说明违反了递增顺序：
- 将chars[i]减一，表示这一位不能保持原值，需要生成更小的递增序列。
- 更新start = i + 1，记录接下来应该全部填充为9的起始位置。
填充9：与之前版本相同，从位置start到字符串的末尾，所有这些位置的字符都被替换为字符’9’。
转换回整数并返回：最后，使用String.valueOf(chars)将字符数组转换回字符串，然后通过Integer.parseInt(...)转换为整数并返回结果。