算法day27-贪心（5）

刘尚恒

目录

1. 合并区间
2. 单调递增的数字
3. 监控二叉树

一、合并区间

https://leetcode.cn/problems/merge-intervals/?envType=problem-list-v2&envId=8At1GmaZ

 

💡 解题思路：

1. 先排序：

   • 按照每个区间的起始点 start 升序排序。

   • 排序后的区间才能方便我们进行逐个合并。

2. 依次遍历区间：

   • 设置两个变量 start 和 end 表示当前合并区间的起止位置。

   • 如果当前遍历到的区间与正在合并的区间存在重叠（即当前区间的起点 ≤ 当前合并区间的终点），则更新 end。

   • 否则说明没有重叠，把当前合并结果加入答案列表，然后重新开始合并。

3. 最后一个区间手动加入：

   • 注意：由于我们只在“发现不重叠”时才把前一个区间加入结果，因此最后一个合并完成的区间会被遗漏，必须在循环外补一次 add()。

代码实现（Java）：

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0){
            return new int[0][0];
        }

        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int xend = intervals[0][1];     //初始化最大边界
        int start = intervals[0][0];
        for(int i=1; i<intervals.length; i++){
            if(intervals[0] <= xend){        //重叠则更新最大边界
                xend = Math.max(xend, intervals[1]);
            }else{          //不重叠，直接加入结果
                res.add(new int[]{start, xend});
                xend = intervals[1];
                start = intervals[0];
            }
        }
        //最后一个合并中的区间不会再进入 if-else 逻辑，所以只能在循环结束后手动添加
        res.add(new int[]{start, xend});    
        return res.toArray(new int[res.size()][]);
    }
}

 📎 时间复杂度分析：

• 排序时间：O(n log n)

• 合并遍历时间：O(n)

• 总复杂度：O(n log n)

二、单调递增的数字

 https://leetcode.cn/problems/monotone-increasing-digits/description/?envType=problem-list-v2&envId=8At1GmaZ

💡 解题思路

我们可以从贪心角度来思考：如果某一位破坏了递增顺序，我们就让它变得更小，并尽可能让后面每一位变大以逼近原始值。

✅ 步骤分解如下：

1. 转字符串 + 字符数组
   为了方便逐位操作，我们将整数转换成字符串，再转为 char[] 数组处理。

2. 从右向左扫描，找出第一个破坏单调的位置
   如果 chars > chars[i + 1]，说明第 i 位比后面一位大了，必须调整。

3. 贪心策略：减当前位 & 后续全设为 '9'

   • 将 chars--，使这一位变小。

   • 为了使整个数字尽可能大，我们将 i+1 之后的所有位都设为 '9'（最大一位数字）。

4. 继续向左处理：可能会产生连锁反应
   有可能 chars-- 后又导致 chars[i - 1] > chars，所以我们从右往左依次检查。

🔢 示例演示

以 n = 3247 为例：

1. 转为字符数组：['3', '2', '4', '7']

2. 3 > 2，第0位比第1位大，出现不合法

3. 将 3-- 变成 2，得到 ['2', '2', '4', '7']

4. 将第1位及之后全设为 '9'，得到：['2', '9', '9', '9']

最终结果是：2999

🧠 为什么后面都设为 '9'？

这是关键点！

• 既然我们已经把高位调小了（chars--），

• 那就希望后面的数尽量大，但不能再破坏单调递增的结构

• '9' 是最大的一位数字，填充在低位最安全

这就构成了一个“高位让步 + 低位尽可能大”的贪心思想。

 Java实现代码：

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

三、监控二叉树

https://leetcode.cn/problems/binary-tree-cameras/description/?envType=problem-list-v2&envId=8At1GmaZ

 

🔍 解题思路：贪心 + 后序遍历

这道题的核心是：从下往上处理，优先在子节点安装摄像头，从而“反过来”覆盖父节点，达到全局最优。

如果你在每个叶子节点都装摄像头，最终会非常浪费；而我们希望让摄像头尽可能多地覆盖节点，尤其是父子同时覆盖。

因此，我们采用后序遍历（左 → 右 → 根）来做贪心决策：
让父节点“兜底”子节点的覆盖，只在必要时才放置摄像头。

---

🏷️ 三种状态设计

我们用整数枚举节点的状态，有如下三种：

状态码	含义
0	当前节点无覆盖（需要被监控）
1	当前节点放置了摄像头
2	当前节点已被覆盖（由子节点的摄像头）

 

🔄 状态转移逻辑（递归）

对当前节点进行递归处理后，根据左右子节点的状态，做出以下判断：

1. 左右子节点都是“被覆盖”状态（2）
   → 当前节点暂时不放摄像头，返回 0，表示无覆盖，交给上层处理。

2. 任一子节点是“无覆盖”状态（0）
   → 当前节点必须放摄像头，返回 1，并摄像头数 +1。

3. 任一子节点是“有摄像头”状态（1）
   → 当前节点自动被覆盖，返回 2。

最后，如果根节点最终是“无覆盖”状态，也需要额外加一个摄像头。

✅ Java 代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int result = 0;
    // 定义状态：
    // 0：该节点无覆盖
    // 1：该节点放置了摄像头
    // 2：该节点有覆盖（来自子节点的摄像头）
    public int minCameraCover(TreeNode root) {
        result = 0;
        if(traversal(root) == 0){
            result++;
        }
        return result;
    }
    public int traversal(TreeNode node){
        //终止条件
        if(node == null){
            return 2;   //空节点视为已覆盖，这样是为了给上一个叶节点返回2的状态
        }
        //这里要用后续遍历
        int left = traversal(node.left);
        int right = traversal(node.right);
        //情况1：左右节点都有覆盖，则该节点（父节点）无覆盖
        if(left == 2 && right == 2){
            return 0;
        }
        //情况2：只要有一个子节点无覆盖，则该节点必须放置摄像头
        if(left == 0 || right == 0){
            result++;
            return 1;
        }
        //情况3：至少有一个子节点放置了摄像头，则该节点被覆盖
        if(left == 1 || right == 1){
            return 2;
        }
        return -1;
    }
}

⏱️ 时间复杂度分析

• 每个节点仅访问一次，递归处理，时间复杂度为：O(n)

• 空间复杂度（递归栈）：O(h)，其中 h 是树的高度

 

来源：https://www.cnblogs.com/xiaoqian01/p/18898101