class Solution {
public:
int minCapability(vector<int>& nums, int k) {
}
};
6346. 打家劫舍 IV
沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。
由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。
小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。
给你一个整数数组 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 <= 1051 <= nums[i] <= 1091 <= k <= (nums.length + 1)/2原站题解
python3 解法, 执行用时: 752 ms, 内存消耗: 28 MB, 提交时间: 2023-09-19 07:43:21
class Solution:
def minCapability(self, nums: List[int], k: int) -> int:
def solve(mx: int) -> int:
cnt = i = 0
while i < len(nums):
if nums[i] > mx: # 不偷
i += 1
else: # 立刻偷
cnt += 1
i += 2 # 跳过下一间房子
return cnt
return bisect_left(range(max(nums)), k, key=solve)
javascript 解法, 执行用时: 112 ms, 内存消耗: 52.1 MB, 提交时间: 2023-09-19 07:41:07
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minCapability = function(nums, k) {
let lower = Math.min(...nums);
let upper = Math.max(...nums);
while (lower <= upper) {
const middle = Math.floor((lower + upper) / 2);
let count = 0;
let visited = false;
for (const x of nums) {
if (x <= middle && !visited) {
count++;
visited = true;
} else {
visited = false;
}
}
if (count >= k) {
upper = middle - 1;
} else {
lower = middle + 1;
}
}
return lower;
};
golang 解法, 执行用时: 176 ms, 内存消耗: 9.2 MB, 提交时间: 2023-02-06 10:18:00
func minCapability(nums []int, k int) int {
return sort.Search(1e9, func(mx int) bool {
f0, f1 := 0, 0
for _, x := range nums {
if x <= mx {
f0, f1 = f1, max(f1, f0+1)
} else {
f0 = f1
}
}
return f1 >= k
})
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 132 ms, 内存消耗: 55.7 MB, 提交时间: 2023-02-06 10:17:39
class Solution {
public:
int minCapability(vector<int> &nums, int k) {
int left = 0, right = *max_element(nums.begin(), nums.end());
while (left + 1 < right) {
int mid = left + (right - left) / 2;
int f0 = 0, f1 = 0;
for (int x : nums)
if (x > mid) f0 = f1;
else {
int tmp = f1;
f1 = max(f1, f0 + 1);
f0 = tmp;
}
(f1 >= k ? right : left) = mid;
}
return right;
}
};
java 解法, 执行用时: 34 ms, 内存消耗: 50.9 MB, 提交时间: 2023-02-06 10:17:21
class Solution {
public int minCapability(int[] nums, int k) {
int left = 0, right = (int) 1e9;
while (left + 1 < right) {
int mid = (left + right) >>> 1;
int f0 = 0, f1 = 0;
for (int x : nums)
if (x > mid) f0 = f1;
else {
int tmp = f1;
f1 = Math.max(f1, f0 + 1);
f0 = tmp;
}
if (f1 >= k) right = mid;
else left = mid;
}
return right;
}
}
python3 解法, 执行用时: 736 ms, 内存消耗: 22.9 MB, 提交时间: 2023-02-06 10:17:01
'''
二分法 + DP
设二分的最大金额为mx，定义f[i]表示在前i个房屋中窃取金额不超过mx的房屋的最大个数。
分类讨论：
不选第i个房屋：f[i]=f[i−1]；
选第i个房屋，前提是金额不超过mx：f[i]=f[i−2]+1。
这两取最大值，即f[i]=max(f[i−1],f[i−2]+1)
代码实现时，可以用两个变量滚动计算。
'''
class Solution:
def minCapability(self, nums: List[int], k: int) -> int:
def check(mx: int) -> int:
f0 = f1 = 0
for x in nums:
if x > mx: f0 = f1
else: f0, f1 = f1, max(f1, f0 + 1)
return f1
return bisect_left(range(max(nums)), k, key=check)