代码随想录day31 | leetcode 56.合并区间 738.单调自增的数字 贪心算法总结篇

56.合并区间

思路

本题的本质其实还是判断重叠区间问题。

Java

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()][]);
    }
}

1. res.getLast() 的作用

res 存储的是已经处理和合并过的区间，而 getLast() 获取的是链表 res 的最后一个区间。
因为：

• 每次合并区间时，总是和当前最后一个区间进行比较。
• 最后一个区间的终点 res.getLast()[1] 代表了当前合并范围的终点。

2. 为什么不能用别的方式替代？

假如不用 res.getLast()，而是直接和所有区间比较（比如 res 中的第一个区间或中间区间），会导致以下问题：

1. 重复比较：代码效率会大幅下降，因为之前的区间已经合并好，没必要再检查。
2. 错误判断：只有 res.getLast() 的终点才代表当前需要合并范围的终点。若使用其他区间的终点，可能会漏掉需要合并的部分。

3.为什么只需要移除最后一个区间？

1. 只与最后一个区间重叠
   假设当前区间 intervals[i] 和结果链表中最后一个区间 res.getLast() 重叠：- 已经合并过的区间（非最后一个）不会和当前区间重叠，因为输入的区间已经按起点排序。
   • 所以，当前区间只需要与 res.getLast() 比较并合并。

举例：

输入区间：

intervals = [[1, 3], [2, 6], [8, 10]]

执行过程：

1. 排序后：[[1, 3], [2, 6], [8, 10]]
2. 初始结果链表 res：

res = [[1, 3]]

3. 当前区间 [2, 6]：- 与 res.getLast() 的 [1, 3] 重叠，合并为 [1, 6]。
   • 移除 res.getLast()（即 [1, 3]），加入合并后的 [1, 6]：

res = [[1, 6]]

4. 下一区间 [8, 10]：- 与 res.getLast()（即 [1, 6]）不重叠，直接加入：

res = [[1, 6], [8, 10]]

最终结果：

[[1, 6], [8, 10]]

为什么不需要移除两个旧区间？

原因 1：已合并的区间是完整的

链表 res 中的所有非最后一个区间，都是与之前的区间合并后的结果，已经是完整的、不可再修改的区间。

• 例如：- [1, 6] 是 [1, 3] 和 [2, 6] 合并后的区间。
  • 当前区间 [8, 10] 不会影响已经合并的 [1, 6]，所以不需要移除或修改非最后一个区间。

原因 2：排序保证了重叠只发生在相邻区间

区间按起点排序后，重叠关系只能发生在当前区间和结果链表中的最后一个区间之间：

• 如果一个区间与链表中较早的区间（非最后一个）重叠，那么这个区间应该已经被合并进最后一个区间了。

总结：只需要移除最后一个区间

• 每次操作只对链表中的最后一个区间（res.getLast()）进行。
• 这是因为，当前区间只可能和最后一个区间重叠，而不可能与链表中的其他区间重叠。
• 因此，移除最后一个区间，然后用合并后的区间替代，已经足够满足逻辑。

738.单调自增的数字

思路

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

Java

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int flag = s.length();  //如果本身就是单调自增的数字(不满足第一个循环的if) 那么flag就不更新为i+1,也就不会通过i < s.length()执行变为9了
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                flag = i+1;
            }
        }
        for (int i = flag; i < s.length(); i++) { //记录最近要变的位置 往后都变
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

为什么这样写不行

for (int i = s.length() - 1; i >= 0; i--) {
    if (chars[i - 1] > chars[i]) {
        chars[i]--;
        flag = i;
    }
}

这样写很符合逻辑 可惜的是

• 当 i = 0 时：- chars[i - 1] 等价于 chars[-1]，试图访问负索引，导致异常。
• Java 不允许访问数组的负索引，所以抛出 ArrayIndexOutOfBoundsException。

贪心算法总结篇

贪心思路往往很巧妙，无固定套路，代码模板。