算法训练营day32 | {56.合并区间, 738.单调递增的数字, 968.监控二叉树}

第八章贪心算法part05，继续练习贪心算法，找出局部最优。

56. 合并区间

1.1 解题分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) return intervals;
        Arrays.sort(intervals, (o1, o2)->Integer.compare(o1[0], o2[0]));
        List<int[]> list = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[i - 1][1]) {
                intervals[i][0] = Math.min(intervals[i - 1][0], intervals[i][0]);
                intervals[i][1] = Math.max(intervals[i - 1][1], intervals[i][1]);
            } else {
                list.add(intervals[i - 1]);
            }
        }
        list.add(intervals[intervals.length - 1]);
        int[][] result = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

738. 单调递增的数字

2.1 解题分析

本题的贪心，贪在哪里比较好想，但是有两个细节问题需要注意：

  1. 考虑遍历顺序，只有从后向前遍历才能重复利用上次比较结果。
  2. 要使用一个flag变量记录最近的需要变为9的位置，并且为了达到最大，其后所有位置都要变成9.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] num = String.valueOf(n).toCharArray();
        int flag = num.length;
        for (int i = num.length - 1; i > 0; i--) {
            if (num[i - 1] > num[i]) {
                num[i - 1]--;
                flag = i;
            }
        }
        for (int i = flag; i < num.length; i++) {
            num[i] = '9';
        }
        return Integer.parseInt(new String(num));
    }
}

968. 监控二叉树

3.1 解题分析

摄像头可以覆盖上中下三层，放在叶子节点就浪费了一层的覆盖范围，同时叶子节点是指数级别的多，能节省的更多。因此从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少。局部最优推出全局最优，且找不出反例，那么按照贪心来。

确定了后序遍历的都遍历顺序后，本题的难点还在于实现如何隔两个节点放一个摄像头？

  • 此时需要状态转移的公式，注意就是单纯的状态转移！每个节点可能有如下三个状态，分别用三个数字来表示：
    • 0：本节点无覆盖
    • 1：本节点有摄像头
    • 2：本节点有覆盖
  • 空节点是什么状态？遍历树都过程中，遇到空节点，应该返回有覆盖状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private int result = 0;

    public int minCameraCover(TreeNode root) {
        if (postOrder(root) == 0) {
            result++;
        }
        return result;
    }

    public int postOrder(TreeNode node) {
        if (node == null) return 2;
        int left = postOrder(node.left);
        int right = postOrder(node.right);

        if (left == 0 || right == 0) {
            result++;
            return 1;
        }
        if (left == 2 && right == 2) return 0;
        if (left == 1 || right == 1) return 2;
        return -1;
    }
}

4. 贪心总结

  • 究竟什么题目是贪心呢？如果找出局部最优并且可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。不过最终会解题就行了。
  • 18道贪心题目罗列&总结
Leetcode > 贪心算法
#Java #代码随想录
算法训练营day32 | {56.合并区间, 738.单调递增的数字, 968.监控二叉树}
http://paopaotangzu.xyz/cn/day32_leetcode/
作者
PROTON TANG
发布于
2026年1月17日
许可协议