LeetCode_二分搜索_中等_2560.打家劫舍 IV

电玩女神 2023-10-16 10:16 77阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋。

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

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums\[i\] 美元。另给你一个整数 k ，表示窃贼将会窃取的最少房屋数。小偷总能窃取至少 k 间房屋。返回小偷的最小窃取能力。

**示例 1：**  
输入：nums = \[2,3,5,9\], k = 2  
输出：5  
解释：  
小偷窃取至少 2 间房屋，共有 3 种方式：

*  窃取下标 0 和 2 处的房屋，窃取能力为 max(nums\[0\], nums\[2\]) = 5 。
 *  窃取下标 0 和 3 处的房屋，窃取能力为 max(nums\[0\], nums\[3\]) = 9 。
 *  窃取下标 1 和 3 处的房屋，窃取能力为 max(nums\[1\], nums\[3\]) = 9 。  
    因此，返回 min(5, 9, 9) = 5。

**示例 2：**  
输入：nums = \[2,7,9,3,1\], k = 2  
输出：2  
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums\[0\], nums\[4\]) = 2 。

**提示：**  
1 <= nums.length <= 105  
1 <= nums\[i\] <= 109  
1 <= k <= (nums.length + 1)/2

## 2.思路 ##

（1）二分搜索  
具体思路参考 [875.爱吃香蕉的珂珂][875.]这篇文章。

相关题目：  
[LeetCode\_动态规划\_中等\_198.打家劫舍][LeetCode_198.]  
[LeetCode\_动态规划\_中等\_213.打家劫舍 II][LeetCode_213._ II]  
[LeetCode\_动态规划\_递归\_二叉树\_中等\_337.打家劫舍 III][LeetCode_337._ III]  
[LeetCode\_二分搜索\_中等\_875.爱吃香蕉的珂珂][875.]  
[LeetCode\_二分搜索\_中等\_2594.修车的最少时间][LeetCode_2594.]

## 3.代码实现（Java） ##

//思路1————二分搜索
    class Solution {
        
        public int minCapability(int[] nums, int k) {
        
            int left = Arrays.stream(nums).min().getAsInt();
            int right = Arrays.stream(nums).max().getAsInt();
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                int cnt = getCnt(nums, mid);
                if (cnt < k) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    
        //在最大金额 amount 的限制下，小偷可以偷取的最大房屋数目
        public int getCnt(int[] nums, int amount) {
        
            int cnt = 0;
            boolean visited = false;
            for (int num : nums) {
        
                if (num <= amount && !visited) {
        
                    cnt++;
                    visited = true;
                } else {
        
                    visited = false;
                }
            }
            return cnt;
        }
    }

[875.]: https://blog.csdn.net/weixin_43004044/article/details/122389933
[LeetCode_198.]: https://blog.csdn.net/weixin_43004044/article/details/123015910
[LeetCode_213._ II]: https://blog.csdn.net/weixin_43004044/article/details/123053121
[LeetCode_337._ III]: https://blog.csdn.net/weixin_43004044/article/details/123093283
[LeetCode_2594.]: https://blog.csdn.net/weixin_43004044/article/details/132730894