打家劫舍 IV【LC2560】
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组
nums表示每间房屋存放的现金金额。形式上，从左起第i间房屋中放有nums[i]美元。另给你一个整数
k，表示窃贼将会窃取的 最少 房屋数。小总能窃取至少k间房屋。返回小偷的 最小 窃取能力。
思路：最小化最大值->二分查找
- 明确题意：求取至少偷
k间不相邻的房屋时，小偷的 最小 窃取能力，即最小化偷取房屋金额的最大值。
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; } }
