本文最后更新于 380 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 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
解法一:二分查找 + 贪心
算法思路:
题意理解:
给定数组
nums
,从中选中一个长度至少为k
的子序列A
,要求A
中没有任何元素在nums
中是相邻的,最小化max(A)
。
解题思路:
我们可以用二分查找的方法来枚举小偷的窃取能力,对于枚举的窃取能力 mx
,我们可与通过贪心的方式判断能否窃取至少 k
间房屋。具体的:
- 考虑到只需要计算个数,在从左至右遍历
nums
时,只要nums[i] <= mx
,我们就可以偷,并且跳过nums[i+1]
例如
nums=[1,2,3,4], mx=3
,如果不偷nums[0]=1
去偷nums[1]=2
,那么只能偷一间房子。而如果偷nums[0]=1
和nums[2]=3
,就可以偷两间房子。
- 如果窃取的房屋数量大于等于
k
,表示答案至多为mx
。 - 否则答案必须超过
mx
。 - 最后二分出来的
mx
即为答案。
代码实现:
class Solution {
public int minCapability(int[] nums, int k) {
int left = 0, right = 0;
for(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;
}
//判断最大值为mid时能否偷k间房屋
private boolean check(int[] nums, int k, int mx){
int cnt = 0, n = nums.length;
for(int i = 0; i < n; i++){
if(nums[i] <= mx) {
cnt ++;
i++; // 跳过下一间房屋
}
}
return cnt >= k;
}
}
复杂度分析:
时间复杂度: O(nlogm),n 为数组 nums 的长度,m 为 nums 的最大值 max(nums)
空间复杂度: O(1)