题目描述
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统,所以小偷 不会窃取相邻的房屋。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额。
给你一个整数数组 nums
表示每间房屋存放的现金金额。形式上,从左起第 i
间房屋中放有 nums[i]
美元。
另给你一个整数数组 k
,表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k
间房屋。
返回小偷的 最小 窃取能力。
样例
输入: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。
输入:nums = [2,7,9,3,1], k = 2
输出:2
解释:共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。
返回 max(nums[0], nums[4]) = 2。
限制
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= (nums.length + 1)/2
算法
(二分答案,贪心) $O(n \log s)$
- 二分盗窃的最大金额 $m$,判定在 $m$ 的限制下,是否可以窃取至少 $k$ 间房屋。
- 可以使用贪心算法判定,从左到右遍历房屋,遇到价值低于 $m$ 的房屋且上一个房屋没有窃取,则可以窃取当前房屋。贪心的正确行可以通过最优构造法证明,假设有了一个最优解,不是按照上述规则生成的,则总可以找到第一个不满足上述规则的房屋,将其按照规则进行置换,解的最优性保持不变。
时间复杂度
- 二分的次数为 $O(\log s)$,其中 $s$ 是最大金额。
- 每次判断的时间复杂度为 $O(n)$。
- 故总时间复杂度为 $O(n \log s)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
private:
int n;
bool check(int m, const vector<int> &nums, int k) {
bool prev = false;
int tot = 0;
for (int i = 0; i < n && tot < k; i++) {
if (nums[i] <= m && !prev) {
tot++;
prev = true;
} else {
prev = false;
}
}
return tot >= k;
}
public:
int minCapability(vector<int>& nums, int k) {
n = nums.size();
int l = 1, r = 1000000000;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid, nums, k)) r = mid;
else l = mid + 1;
}
return l;
}
};