算法day27-贪心（5）

刘尚恒 發表於 2025-5-27 12:00:00

<h1>目录</h1>
<ol>
<li>合并区间</li>
<li>单调递增的数字</li>
<li>监控二叉树</li>
</ol>
<h2>一、合并区间</h2>
https://leetcode.cn/problems/merge-intervals/?envType=problem-list-v2&envId=8At1GmaZ
<img src="https://img2024.cnblogs.com/blog/2297173/202505/2297173-20250527100735891-1108881220.png">
 
<h3 data-start="256" data-end="268">💡 解题思路：</h3>
<ol data-start="270" data-end="593">
<li data-start="270" data-end="336">
先排序：
<ul data-start="285" data-end="336">
<li data-start="285" data-end="311">
按照每个区间的起始点 <code data-start="298" data-end="305">start</code> 升序排序。
</li>
<li data-start="315" data-end="336">
排序后的区间才能方便我们进行逐个合并。
</li>
</ul>
</li>
<li data-start="338" data-end="498">
依次遍历区间：
<ul data-start="356" data-end="498">
<li data-start="356" data-end="395">
设置两个变量 <code data-start="365" data-end="372">start</code> 和 <code data-start="375" data-end="380">end</code> 表示当前合并区间的起止位置。
</li>
<li data-start="399" data-end="460">
如果当前遍历到的区间与正在合并的区间存在重叠（即当前区间的起点 ≤ 当前合并区间的终点），则更新 <code data-start="454" data-end="459">end</code>。
</li>
<li data-start="464" data-end="498">
否则说明没有重叠，把当前合并结果加入答案列表，然后重新开始合并。
</li>
</ul>
</li>
<li data-start="500" data-end="593">
最后一个区间手动加入：
<ul data-start="522" data-end="593">
<li data-start="522" data-end="593">
注意：由于我们只在“发现不重叠”时才把前一个区间加入结果，因此最后一个合并完成的区间会被遗漏，必须在循环外补一次 <code data-start="585" data-end="592">add()</code>。
</li>
</ul>
</li>
</ol>
代码实现（Java）：
<div class="cnblogs_code">
<pre>class Solution {
public int[][] merge(int[][] intervals) {
 if(intervals.length == 0){
 return new int;
 }

 List<int[]> res = new ArrayList<>();
 Arrays.sort(intervals,(a,b)->Integer.compare(a,b));
 int xend = intervals; //初始化最大边界
 int start = intervals;
 for(int i=1; i<intervals.length; i++){
 if(intervals <= xend){ //重叠则更新最大边界
 xend = Math.max(xend, intervals);
 }else{ //不重叠，直接加入结果
 res.add(new int[]{start, xend});
 xend = intervals;
 start = intervals;
 }
 }
 //最后一个合并中的区间不会再进入 if-else 逻辑，所以只能在循环结束后手动添加
 res.add(new int[]{start, xend});
 return res.toArray(new int[]);
}
}</pre>
</div>
 📎 时间复杂度分析：
<ul>
<li data-start="1438" data-end="1457">
排序时间：<code data-start="1445" data-end="1457">O(n log n)</code>
</li>
<li data-start="1458" data-end="1473">
合并遍历时间：<code data-start="1467" data-end="1473">O(n)</code>
</li>
<li data-start="1474" data-end="1493">
总复杂度：<code data-start="1481" data-end="1493">O(n log n)</code>
</li>
</ul>
<h2>二、单调递增的数字</h2>
 https://leetcode.cn/problems/monotone-increasing-digits/description/?envType=problem-list-v2&envId=8At1GmaZ
<img src="https://img2024.cnblogs.com/blog/2297173/202505/2297173-20250527103657588-1362668197.png">
<h3 data-start="246" data-end="257">💡 解题思路</h3>
我们可以从贪心角度来思考：如果某一位破坏了递增顺序，我们就让它变得更小，并尽可能让后面每一位变大以逼近原始值。
<h4 data-start="320" data-end="334">✅ 步骤分解如下：</h4>
<ol data-start="336" data-end="688"><ol data-start="336" data-end="688">
<li data-start="336" data-end="399">
转字符串 + 字符数组 
为了方便逐位操作，我们将整数转换成字符串，再转为 <code data-start="385" data-end="393">char[]</code> 数组处理。

</li>
<li data-start="401" data-end="484">
从右向左扫描，找出第一个破坏单调的位置 
如果 <code data-start="436" data-end="461">chars > chars</code>，说明第 <code data-start="466" data-end="469">i</code> 位比后面一位大了，必须调整。

</li>
<li data-start="486" data-end="596">
贪心策略：减当前位 & 后续全设为 '9'
<ul data-start="520" data-end="596">
<li data-start="520" data-end="544">
将 <code data-start="524" data-end="536">chars--</code>，使这一位变小。

</li>
<li data-start="548" data-end="596">
为了使整个数字尽可能大，我们将 <code data-start="566" data-end="571">i+1</code> 之后的所有位都设为 <code data-start="582" data-end="587">'9'</code>（最大一位数字）。

</li>

</ul>

</li>
<li data-start="598" data-end="688">
继续向左处理：可能会产生连锁反应 
有可能 <code data-start="631" data-end="643">chars--</code> 后又导致 <code data-start="649" data-end="674">chars > chars</code>，所以我们从右往左依次检查。

</li>

</ol></ol>
<h3 data-start="695" data-end="706">🔢 示例演示</h3>
以 <code data-start="710" data-end="720">n = 3247</code> 为例：
<ol data-start="726" data-end="878">
<li data-start="726" data-end="758">
转为字符数组：<code data-start="736" data-end="758">['3', '2', '4', '7']</code>
</li>
<li data-start="759" data-end="788">
<code data-start="762" data-end="769">3 > 2</code>，第0位比第1位大，出现不合法
</li>
<li data-start="789" data-end="832">
将 <code data-start="794" data-end="799">3--</code> 变成 <code data-start="803" data-end="806">2</code>，得到 <code data-start="810" data-end="832">['2', '2', '4', '7']</code>
</li>
<li data-start="833" data-end="878">
将第1位及之后全设为 <code data-start="847" data-end="852">'9'</code>，得到：<code data-start="856" data-end="878">['2', '9', '9', '9']</code>
</li>
</ol>
最终结果是：2999
<h3 data-start="1451" data-end="1473">🧠 为什么后面都设为 <code data-start="1467" data-end="1472">'9'</code>？</h3>
这是关键点！
<ul data-start="1483" data-end="1570">
<li data-start="1483" data-end="1512">
既然我们已经把高位调小了（<code data-start="1498" data-end="1510">chars--</code>），
</li>
<li data-start="1513" data-end="1544">
那就希望后面的数尽量大，但不能再破坏单调递增的结构
</li>
<li data-start="1545" data-end="1570">
<code data-start="1547" data-end="1552">'9'</code> 是最大的一位数字，填充在低位最安全
</li>
</ul>
这就构成了一个“高位让步 + 低位尽可能大”的贪心思想。
 Java实现代码：
<div class="cnblogs_code">
<pre>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) {
 chars--;
 start = i + 1;
 }
 }

 for (int i = start; i < chars.length; i++) {
 chars = '9';
 }

 return Integer.parseInt(new String(chars));
}
}</pre>
</div>
<h2>三、监控二叉树</h2>
https://leetcode.cn/problems/binary-tree-cameras/description/?envType=problem-list-v2&envId=8At1GmaZ
<img src="https://img2024.cnblogs.com/blog/2297173/202505/2297173-20250527110755645-1225096784.png">
 
<h3 data-start="228" data-end="249">🔍 解题思路：贪心 + 后序遍历</h3>
这道题的核心是：从下往上处理，优先在子节点安装摄像头，从而“反过来”覆盖父节点，达到全局最优。
如果你在每个叶子节点都装摄像头，最终会非常浪费；而我们希望让摄像头尽可能多地覆盖节点，尤其是父子同时覆盖。
因此，我们采用后序遍历（左 → 右 → 根）来做贪心决策： 
让父节点“兜底”子节点的覆盖，只在必要时才放置摄像头。
<hr data-start="432" data-end="435">
<h3 data-start="437" data-end="451">🏷️ 三种状态设计</h3>
我们用整数枚举节点的状态，有如下三种：
<div class="_tableContainer_16hzy_1">
<div class="_tableWrapper_16hzy_14 group flex w-fit flex-col-reverse">
<div>
<table style="height: 126px; width: 822px">
<thead>
<tr><th>状态码</th><th>含义</th></tr>
</thead>
<tbody>
<tr>
<td><code>0</code></td>
<td>当前节点无覆盖（需要被监控）</td>
</tr>
<tr>
<td><code>1</code></td>
<td>当前节点放置了摄像头</td>
</tr>
<tr>
<td><code>2</code></td>
<td>当前节点已被覆盖（由子节点的摄像头）</td>
</tr>
</tbody>
</table>
</div>
<div> </div>
<div>
<h3 data-start="595" data-end="612">🔄 状态转移逻辑（递归）</h3>
对当前节点进行递归处理后，根据左右子节点的状态，做出以下判断：
<ol data-start="647" data-end="824">
<li data-start="647" data-end="711">
左右子节点都是“被覆盖”状态（2） 
→ 当前节点暂时不放摄像头，返回 <code data-start="694" data-end="697">0</code>，表示无覆盖，交给上层处理。

</li>
<li data-start="713" data-end="773">
任一子节点是“无覆盖”状态（0） 
→ 当前节点必须放摄像头，返回 <code data-start="758" data-end="761">1</code>，并摄像头数 <code data-start="768" data-end="772">+1</code>。

</li>
<li data-start="775" data-end="824">
任一子节点是“有摄像头”状态（1） 
→ 当前节点自动被覆盖，返回 <code data-start="820" data-end="823">2</code>。

</li>

</ol>
最后，如果根节点最终是“无覆盖”状态，也需要额外加一个摄像头。
✅ Java 代码实现
</div>
<div>
<div class="cnblogs_code">
<pre>/**
* 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;
}
}</pre>
</div>
<h3 data-start="1554" data-end="1568">⏱️ 时间复杂度分析</h3>
<ul data-start="1570" data-end="1639">
<li data-start="1570" data-end="1604">
每个节点仅访问一次，递归处理，时间复杂度为：O(n)
</li>
<li data-start="1605" data-end="1639">
空间复杂度（递归栈）：O(h)，其中 <code data-start="1630" data-end="1633">h</code> 是树的高度
</li>
</ul>
 
</div>
</div>
</div> 
来源：https://www.cnblogs.com/xiaoqian01/p/18898101

頁: [1]

琼殿技术论坛's Archiver

算法day27-贪心（5）