题目描述
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统,所以小偷不会窃取相邻的房屋。
小偷的窃取能力定义为他在窃取过程中能从单间房屋中窃取的最大金额。
给你一个整数数组$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 \leq nums.length \leq 10^5$
- $1 \leq nums[i] \leq 10^9$
- $1 \leq k \leq \frac{nums.length + 1}{2}$
算法
这个题目还是很好的,结合了二分答案和动态规划,是一道全新版本的“打家劫舍”。
二分答案
看到题目中要最小化最大值就能想到二分答案,这已经是典中典了。先分析一下单调性,如果偷窃上限为$mx$时,能够保证至少盗窃$k$间互不相邻的房子,那么$mx$更大时肯定也能满足偷窃的房子数不少于$k$,因为限制更弱了。因此,整体的框架就是二分答案,对于给定的上界$mx$:
- 如果此时保证至少能偷不少于$k$间互不相邻房子,那么更大的$mx$就不用再考虑了。但是当前的$mx$有可能是答案,因此记录一下,然后直接舍弃掉右半部分往左搜索;
- 否则$mx$给的限制太强,需要往右边搜索。
动态规划
关键是如何判断在给定上界$mx$下,最多能偷窃的互不相邻的房子的最大数量,采用动态规划来求解。
状态定义
$dp[i][0]$和$dp[i][1]$分别表示,当考虑屋子$[0,i]$时,不偷$house_i$或偷$house_i$能够偷窃的最多房子数。
状态转移
-
如果$house_i \leq mx$那么当前房子是可偷可不偷的,如果偷,那么$house_{i-1}$就不能偷,状态转移方程为
$dp[i][0]=max(dp[i-1][0],dp[i-1][1])$
$dp[i][1]=dp[i-1][0]+1$ -
如果$house_i \gt mx$那么当前房子就不能偷,$dp[i][1]=0$,只存在状态转移$dp[i][0]=max(dp[i - 1][0], dp[i - 1][1])$。
在线性$DP$的过程中,只要发现$max(dp[i][0],dp[i][1]) \geq k$,就表示在上界$mx$的限制下能够偷至少$k$个互不相邻的房子。
复杂度分析
二分范围是$[minVal,maxVal]$,其中$minVal$和$maxVal$分别是$nums$中的最小值和最大值。求得两个最值的时间复杂度为$O(n)$,需要遍历一遍数组。$check$函数的内部是线性$DP$,时间复杂度为$O(n)$。因此总体的时间复杂度为$O(n)+O(nlog_2(maxVal-minVal))$。
每进行一次$check$就要开辟一个$O(n)$级别的$DP$数组(由于每个状态只依赖前面一个状态,因此这个空间也可以优化到$O(1)$),所以额外空间复杂度为$O(nlog_2(maxVal-minVal))$。
C++ 代码
class Solution {
public:
int minCapability(vector<int>& nums, int k) {
int left = *min_element(nums.begin(), nums.end()), right = *max_element(nums.begin(), nums.end());
while(left < right) {
int mid = left + ((right - left) >> 1);
if(check(nums, mid, k)) {
right = mid;
}else {
left = mid + 1;
}
}
return left;
}
bool check(vector<int>& nums, int mx, int k) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(2));
dp[0][1] = nums[0] <= mx;
if(dp[0][1] >= k) return true;
for(int i = 1; i < n; i++) {
if(nums[i] > mx) {
// 当前房屋不能偷
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); // 前一个可偷可不偷
}else {
// 当前房屋能偷
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + 1;
}
if(max(dp[i][0], dp[i][1]) >= k) return true;
}
return false;
}
};