2560. 打家劫舍 IV

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

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

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

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

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

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

最小化最大值与最大化最小值，建议使用二分法做
该题的主要思想是遍历nums[i]选择满足条件的最小窃取能力，很自然会想到使用二分法降低时间复杂度。使用二分法遍历每种可能的窃取能力，看看能否满足条件，不满足，移动left或者right。
用f[i]记录nums[0]~nums[i]之间选择的房屋数量。对于每种可能的窃取能力，看看相应的f能否大于或等于k。

class Solution {/**最小化最大值与最大化最小值，建议使用二分法做该题的主要思想是遍历nums[i]选择满足条件的最小窃取能力，很自然会想到使用二分法降低时间复杂度。使用二分法遍历每种可能的窃取能力，看看能否满足条件，不满足，移动left或者right。用f[i]记录nums[0]~nums[i]之间选择的房屋数量。对于每种可能的窃取能力，看看相应的f能否大于或等于k。*/public int minCapability(int[] nums, int k) {int left = 0, right = 0;// 确定rightfor(int num:nums) {right = Math.max(right, num);}// 二分遍历所有的窃取能力while(left+1<right) {int mid = (left+right)>>1;// 满足看看能不能下移if(check(nums, k, mid)) {right = mid;} else {left = mid;}}return right;}public boolean check(int[] nums, int k, int mx) {int cur = 0, prev = 0;// 大于当前窃取能力，不选for(int num:nums) {if(num>mx) {prev = cur;} // 小于当前窃取能力，选else {int tmp = cur;cur = Math.max(cur, prev+1);prev = tmp;}}return cur>=k;}
}