2560. 打家劫舍 IV (opens new window)

1.二分查找+贪心+最小最大问题

思路：题目要求的是打劫金额，因此二分枚举房子的金额，思路如下：

• 下界是房间金额数的最小值，上界是房间金额数的最大值
• 枚举房间金额数量mid，贪心计算所有房间偷窃金额在小于mid的情况，可偷窃的最大房间数量：
  • 只要前一个房间没有偷过，当前房间的金额数量小于mid，那么房间计数+1，访问位置为true
  • 如果当前房间的①金额数量②相邻状态不符合要求，则不进行偷窃，访问位置为false
• 如果当前count小于k，说明当前枚举金额mid太小了，需要扩大下界。如果当前count大于k，则说需要减小上界。

为什么计算最大房间数量可以使用贪心？

• 不同于计算最大金额总数，当前房间可以偷窃时如果选择偷，那么可能会因为相邻限制，错过下一个房间更大的金额数。

• 在房间数量统计问题上，只要当前可以偷那就直接偷窃，因为本来当前房间和下一个房间偷窃时就是只能二选一，做不到两个都偷。相反如果当前不偷窃，而选择偷下一个房间，那么很有可能错过下下一个房间。

如何保证最后得到的结果一定会出现在nums当中？

因为在本问题中，枚举的对象并不是数组nums出现的每个元素，而是从【min,max】所有数的范围内寻找，使用二分查找往往需要满足单调性质。即偷窃金额小于k+1的可偷窃最大房间数量，一定会比偷窃金额小于k的可偷窃最大房间数量要大。

因为题目肯定有解，并且解是nums具体的一个的数target，也就是说mid=target时能够满足可偷窃房间数正好等于k，那么二分枚举时mid>target对应的房间数必然大于等于k，那么会mid会继续逼近target。下界同理。

✨最大最小问题往二分查找上面靠

class Solution {
    public int minCapability(int[] nums, int k) {
        int high=Integer.MIN_VALUE,low=Integer.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            high=Math.max(high,nums[i]);
            low=Math.min(low,nums[i]);
        }
        while(low<high){
            int mid=(low+high)>>1;
            //贪心计算小于mid的最大偷窃房子个数
            boolean visit=false;
            int count=0;
            for(int i=0;i<nums.length;i++){
                if(nums[i]<=mid&&!visit){
                    count++;
                    visit=true;
                }
                else  visit=false;
            }

            if(count<k) low=mid+1;
            else high=mid;
        }
        return low;
    }
}