2560-打家劫舍 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 <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= (nums.length + 1)/2

前置知识：二分

见 【基础算法精讲 04】 ，详细介绍了二分的原理及实现。

思路

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

为什么？一般来说，二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，有单调性，可以二分。

类似的题目在先前的周赛中出现过多次，例如：

• 2439. 最小化数组中的最大值
• 2513. 最小化两个数组中的最大值
• 2517. 礼盒的最大甜蜜度
• 2528. 最大化城市的最小供电站数目

然后就可以像 198. 打家劫舍 那样写一个 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)

代码实现时，可以用两个变量滚动计算。

附：视频讲解

[sol1-Python3]

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)

[sol1-Java]

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;
    }
}

[sol1-C++]

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;
    }
};

[sol1-Go]

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 }

复杂度分析

• 时间复杂度：O(n\log U)，其中 n 为 nums 的长度，U=max(\textit{nums})。
• 空间复杂度：O(1)。