代码随想录算法训练营第三十四天|56. 合并区间、738.单调递增的数字、968.监控二叉树

56. 合并区间

题目链接：56. 合并区间
文档讲解：代码随想录
状态：无语，这题从右边界排序做不了！

思路：

1. 排序：按照区间的起始位置进行排序，这样后面处理时可以顺序合并重叠区间。
2. 合并：从第一个区间开始，依次检查每个区间是否与前一个区间重叠。
   • 如果重叠，就更新前一个区间的结束位置为当前区间的结束位置的最大值。
   • 如果不重叠，就将前一个区间加入结果列表，并更新当前区间为新的待合并区间。
3. 收尾：遍历完所有区间后，将最后一个待合并的区间加入结果列表。

题解：

    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        // 按照区间的起始位置进行升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> list = new ArrayList<>();
        int[] pre = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];

            // 如果当前区间的起始位置小于等于前一个区间的结束位置，合并区间
            if (cur[0] <= pre[1]) {
                pre[1] = Math.max(cur[1], pre[1]); // 更新合并后的结束位置
            } else {
                list.add(pre); // 将前一个合并后的区间加入结果列表
                pre = cur; // 更新为当前区间，准备合并下一个区间
            }
        }

        list.add(pre); // 添加最后一个合并后的区间

        // 将结果转换为二维数组并返回
        return list.toArray(new int[list.size()][]);
    }

738.单调递增的数字

题目链接：738.单调递增的数字
文档讲解：代码随想录
状态：做出来了，但是比较费力。。。

思路：通过从后向前遍历整数的每一位，检查是否需要调整前一位来保持递增性，然后将需要调整的位置后的所有位数设为 ‘9’，最终返回调整后的整数值。

题解：

    public int monotoneIncreasingDigits(int n) {
        char[] chars = String.valueOf(n).toCharArray(); // 将整数 n 转换为字符数组
        int index = chars.length; // 初始化索引为字符数组的长度
        for (int i = chars.length - 1; i > 0; i--) { // 从倒数第二位开始向前遍历字符数组
            if (chars[i - 1] > chars[i]) { // 如果前一位大于当前位
                chars[i - 1]--; // 将前一位减 1
                index = i; // 更新索引为当前位置
//                不能使用chars[i] = '9',如100,就会出现90,正确答案是99
            }
        }
        for (int i = index; i < chars.length; i++) { // 从索引位置开始向后遍历字符数组
            chars[i] = '9'; // 将后面的所有位数设为 9
        }
        String s = String.valueOf(chars); // 将字符数组转换为字符串
        return Integer.parseInt(s); // 将字符串转换为整数并返回
    }

968.监控二叉树

题目链接：968.监控二叉树
文档讲解：代码随想录
状态：留着二刷