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

打家劫舍 IV【LC2560】

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

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

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

给你一个整数数组 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;
      }
  
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34

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