Medium

题目描述

在一条街上有若干连续的房屋，每间房屋都有一些钱。有一个强盗想要从这些房屋中偷钱，但他拒绝从相邻的房屋中偷窃。

强盗的能力值定义为他从所有被偷的房屋中偷到的最大金额。

给你一个整数数组 nums 表示每间房屋中存放的金额。更正式地说，从左边起第 i 间房屋中有 nums[i] 美元。

同时给你一个整数 k，表示强盗将要偷窃的房屋的最少数量。保证总是可以偷窃至少 k 间房屋。

返回在所有可能的偷窃至少 k 间房屋的方案中，强盗的最小能力值。

示例 1：

输入: nums = [2,3,5,9], k = 2
输出: 5
解释: 
偷窃至少 2 间房屋有以下三种方案:
- 偷窃下标 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

解题思路

这道题的关键在于理解"能力值"的定义：强盗偷窃的所有房屋中的最大金额。我们需要找到偷窃至少k间房屋的所有方案中，能力值的最小值。

思路分析：

这是一个经典的二分搜索 + 贪心验证的问题。直接枚举所有可能的偷窃方案复杂度太高，我们需要换个角度思考。

关键观察：如果我们固定能力值为某个值mid，那么我们只能偷窃金额不超过mid的房屋。此时问题转化为：在不偷窃相邻房屋的约束下，最多能偷窃多少间金额不超过mid的房屋？

二分搜索策略：

  • 搜索范围：[min(nums), max(nums)]
  • 对于每个中间值mid，检查能否偷窃至少k间金额不超过mid的房屋
  • 如果可以，说明答案可能更小，向左搜索；否则向右搜索

贪心验证： 对于给定的能力值mid，使用贪心策略验证：从左到右遍历，如果当前房屋金额不超过mid且与前一个偷窃的房屋不相邻，就偷窃它。这样可以获得最多的偷窃数量。

这种方法的正确性在于：如果存在一种偷窃方案使得能力值不超过mid且偷窃数量至少为k，那么贪心策略一定能找到这样的方案。

代码实现

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int left = *min_element(nums.begin(), nums.end());
        int right = *max_element(nums.begin(), nums.end());
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canRob(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
private:
    bool canRob(vector<int>& nums, int k, int maxCapability) {
        int count = 0;
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] <= maxCapability) {
                count++;
                i += 2;  // 跳过下一个相邻房屋
            } else {
                i++;
            }
        }
        return count >= k;
    }
};

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def canRob(maxCapability):
            count = 0
            i = 0
            while i < len(nums):
                if nums[i] <= maxCapability:
                    count += 1
                    i += 2  # 跳过下一个相邻房屋
                else:
                    i += 1
            return count >= k
        
        left, right = min(nums), max(nums)
        
        while left < right:
            mid = (left + right) // 2
            if canRob(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int MinCapability(int[] nums, int k) {
        int left = nums.Min();
        int right = nums.Max();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CanRob(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private bool CanRob(int[] nums, int k, int maxCapability) {
        int count = 0;
        int i = 0;
        while (i < nums.Length) {
            if (nums[i] <= maxCapability) {
                count++;
                i += 2;  // 跳过下一个相邻房屋
            } else {
                i++;
            }
        }
        return count >= k;
    }
}

var minCapability = function(nums, k) {
    const canRob = (maxCapability) => {
        let count = 0;
        let i = 0;
        while (i < nums.length) {
            if (nums[i] <= maxCapability) {
                count++;
                i += 2;  // 跳过下一个相邻房屋
            } else {
                i++;
            }
        }
        return count >= k;
    };
    
    let left = Math.min(...nums);
    let right = Math.max(...nums);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canRob(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n log(max(nums) - min(nums)))
空间复杂度O(1)

说明：

  • 二分搜索的范围是 [min(nums), max(nums)]，最多需要 log(max(nums) - min(nums)) 次迭代
  • 每次验证需要 O(n) 时间遍历数组
  • 只使用了常数额外空间

相关题目