2560. 打家劫舍 IV

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.

The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array nums representing how much money is stashed in each house. More formally, the ith house from the left has nums[i] dollars.

You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.

Return the minimum capability of the robber out of all the possible ways to steal at least k houses.

Example 1:

Input: nums = [2,3,5,9], k = 2

Output: 5

Explanation:

There are three ways to rob at least 2 houses:

• Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
• Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
• Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.

Therefore, we return min(5, 9, 9) = 5.

Example 2:

Input: nums = [2,7,9,3,1], k = 2

Output: 2

Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= (nums.length + 1)/2

题目大意

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 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 <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= (nums.length + 1)/2

解题思路

1. 确定搜索范围：

   • 最小值 left = min(nums)（最小房子价值）。
   • 最大值 right = max(nums)（最大房子价值）。

2. 二分 mid = (left + right) / 2，表示尝试以 mid 作为所选房子的最大价值：

   • 能否选择 k 个房子，使得最大值 ≤ mid？
     • 遍历 nums，采用贪心策略 (canStealKHouses(cap))：
       • 如果当前房子价值 ≤ mid，则偷该房子，并跳过下一个房子（避免相邻）。
       • 否则，跳过该房子。
     • 统计偷取的房子数量 count，如果 count ≥ k，说明 mid 可行。
   • 若 mid 可行，尝试更小的 mid，调整 right = mid。
   • 若 mid 不可行，尝试更大的 mid，调整 left = mid + 1。

3. 最终返回最小可行的 mid。

复杂度分析

• 时间复杂度：O(n log M)

  • 二分查找 O(log M)，其中 M = max(nums) - min(nums)。
  • 每次检查 O(n)，canStealKHouses 遍历 nums 计算是否满足条件。
  • 总复杂度 O(n log M)。

• 空间复杂度：O(1)，仅使用常数个变量。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minCapability = function (nums, k) {
	const canStealKHouses = (cap) => {
		let count = 0;
		let i = 0;
		while (i < nums.length) {
			if (nums[i] <= cap) {
				if (++count >= k) return true;
				i += 2;
			} else {
				i++;
			}
		}
		return false;
	};

	let left = Math.min(...nums);
	let right = Math.max(...nums);

	while (left < right) {
		const mid = ((left + right) / 2) | 0;
		if (canStealKHouses(mid)) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};

相关题目

题号	标题	题解	标签	难度	力扣
11	盛最多水的容器	[✓]	贪心 数组 双指针	🟠	🀄️ 🔗
198	打家劫舍	[✓]	数组 动态规划	🟠	🀄️ 🔗