【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

打家劫舍 IV【LC2560】

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的最少房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的最小窃取能力。

思路：最小化最大值->二分查找
- 明确题意：求取至少偷k间不相邻的房屋时，小偷的最小窃取能力，即最小化偷取房屋金额的最大值。
- 寻找单调性（二段性）：偷取能力 $y$ 增加（能偷取的房屋的金额必须小于等于 $y$ ），能偷取不相邻房屋数目增加，因此一定存在一个分割点 $y$ ，使得
  - 小于y的值，能够偷取的房屋数目 $co u n t$ 必然不满足 $\ge k$ ；
  - 大于等于y的值，能够偷取的房屋数目 $co u n t$ 必然满足 $\ge k$ 。
- 二分答案：因此当偷取房屋数目至少为 $k$ 时，寻找最大偷取数目的最小值 $y$ ，可以通过二分查找的方法找到最终的 $y$ ，二分查找的下限为min(nums)，上限为max(nums)
- check函数：
  - 统计最大偷取数目为 $y$ 时，能够偷取的房屋数目，是否大于 $k$ ，大于则返回true
  - 由于不能偷取相邻房屋，因此需要记录上一个偷取的房屋编号
实现文章来源地址https://www.toymoban.com/news/detail-732127.html
```
class Solution {
    public int minCapability(int[] nums, int k) {
        int n = nums.length;
        int l = Integer.MIN_VALUE, r = 0;
        for (int num : nums){
            r = Math.max(r, num);
            l = Math.min(l, num);            
        }
        while (l <= r){
            int mid = (l + r) / 2;
            if (check(nums, mid, k)){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;

    }
    public boolean check(int[] nums, int target, int k){
        int n = nums.length;
        int j = -2;
        int count = 0;
        for (int i = 0; i < n; i++){
            if (j + 2 <= i && nums[i] <= target){
                count++;
                j = i;
                if (count >= k) return true;
            }     
        }
        return false;
    }

}
```
- 复杂度
  - 时间复杂度： $O(n\log C)$ ， $n$ 是数组的长度，C是二分的范围，即数组中最最大和最小值的差值。二分查找的时间复杂度是 $O(\log C)$ ，每次二分查找需要判断是否符合条件的时间复杂度为 $O (n)$ ，因此总的时间复杂度为 $O (n l o g (n c))$
  - 空间复杂度： $O (1)$