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

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

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

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

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

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

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

• 思路：最小化最大值->二分查找

  • 明确题意：求取至少偷k间不相邻的房屋时，小偷的 最小 窃取能力，即最小化偷取房屋金额的最大值。
  • 寻找单调性（二段性）：偷取能力$y$增加（能偷取的房屋的金额必须小于等于$y$），能偷取不相邻房屋数目增加，因此一定存在一个分割点$y$，使得
    • 小于y的值，能够偷取的房屋数目 $count$必然不满足 $count\ge k$；
    • 大于等于y的值，能够偷取的房屋数目 $count$必然满足 $total\ge k$。
  • 二分答案：因此当偷取房屋数目至少为$k$时，寻找最大偷取数目的最小值$y$，可以通过二分查找的方法找到最终的$y$，二分查找的下限为min(nums)，上限为max(nums)
  • check函数：
    • 统计最大偷取数目为$y$时，能够偷取的房屋数目，是否大于$k$，大于则返回true
    • 由于不能偷取相邻房屋，因此需要记录上一个偷取的房屋编号

• 实现

  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(nlog(nc))$
    • 空间复杂度：$O(1)$