题目描述
leetcode 中等题
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。
另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。
返回小偷的 最小 窃取能力。
示例1：
1
2
3
4
5
6
7
8
| 输入：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 。
|
提示1：
1
2
3
| 1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= (nums.length + 1)/2
|
二分 + DP
看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。
注意到窃取房屋数和窃取能力满足单调性，所以可以二分窃取能力，取满足条件的最小值（右边界）即可，也就是满足至少偷窃 $k$ 间房屋。
具体来说，定义 $get(max)$ 返回窃取能力不超过 $max$ 时最多能偷窃的房屋数，如果某个 $max$ 大于等于题目中的 $k$ ，那么显然 $max$ 的右边都满足题意，所以可以继续缩小右边界，反之类似。
剩下问题就是 $get(max)$ 的实现了，可以通过动态规划解决，定义 $dp[i]$ 表示前 $i$ 个房子窃取能力不超过 $max$ 时的最大房屋数，那么有：
- 第 i 个房子不偷，此时 $dp[i] = dp[i - 1]$
- 第 i 个房子偷，需满足 $nums[i] <= max$ ，此时 $dp[i] = dp[i - 2] + 1$
取两者最大值即可
$$
\begin{align}
&dp[i] = max(dp[i - 1], dp[i - 2] + 1)
\end{align}
$$
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
| class Solution {
public int minCapability(int[] nums, int k) {
int n = nums.length;
int left = 0, right = 1000000000;
while(left < right){
int mid = left + (right - left >> 1);
if(get(mid, nums) < k){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
private int get(int max, int[] nums){
int n = nums.length;
int[] dp = new int[n + 2];
for(int i = 2; i <= n + 1; i++){
dp[i] = dp[i - 1];
if(nums[i - 2] <= max){
dp[i] = Math.max(dp[i], dp[i - 2] + 1);
}
}
return dp[n + 1];
}
}
|
可以滚动变量
1
2
3
4
5
6
7
8
9
10
11
| ...
private int getMaxHouse(int maxSteal, int[] nums){
int pre2 = 0, pre1 = 0;
for(int i = 0; i < nums.length; i++){
int cur = nums[i] <= maxSteal ? Math.max(pre1, pre2 + 1) : pre1;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
...
|
二分 + 贪心
另一种解法是二分 + 贪心，二分的过程同上。
而对于求窃取能力不超过 $mid$ 时最多能偷窃的房屋数，可以顺序的遍历房屋，如果某个房屋小于 $mid$ 时，贪心的偷取该房子即可。
直觉上就是正确的，也可以证明：因为 $dp[i - 1] = max(dp[i - 2] , dp[ i - 3] + 1)$ ，且显然有 $dp[i] >= dp[i - 1]$ ，也就是说 $dp[i - 2] >= dp[i - 3]$ ，可以得出 $dp[i - 1] <= max(dp[i - 2], dp[i - 2] + 1)$ ，即 $dp[i - 1] <= dp[i - 2] + 1$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int minCapability(int[] nums, int k) {
int left = 0, right = 1000000000;
while(left < right){
int mid = left + (right - left >> 1), curK = 0;
for(int i = 0; i < nums.length; i += nums[i] > mid ? 1 : 2){
curK += nums[i] <= mid ? 1 : 0;
}
if(curK < k){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
}
|