打家劫舍 IV

标签: 数组 二分查找

难度: Medium

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

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

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

给你一个整数数组 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

Submission

运行时间: 238 ms

内存: 26.6 MB


def least_houses(nums, cap):
    """leetcode
    """
    count, visited = 0, False
    for x in nums:
        if x <= cap and not visited:
            count, visited = count + 1, True
        else:
            visited = False
    return count


def house_robber_iv_binary_greedy(nums, k):
    start, end = min(nums), max(nums)
    least = 0
    while start <= end:
        middle = (start + end) // 2
        res = least_houses(nums, middle)
        if res >= k:
            least = middle
            end = middle - 1
        else:
            start = middle + 1
    return least



class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        return house_robber_iv_binary_greedy(nums, k)

Explain

这道题的题解使用了二分查找配合贪心算法的策略来解决问题。首先，定义了一个辅助函数 `least_houses`，该函数计算在给定的最大能力 `cap` 下，小偷最多可以窃取的房屋数。这个函数通过遍历数组 `nums`，每当遇到一个不超过 `cap` 的值且前一个房屋没有被窃取时，增加计数器。主函数 `house_robber_iv_binary_greedy` 通过二分查找来确定最小的窃取能力。它将最小值设为数组中的最小值，最大值设为数组中的最大值。然后，使用二分查找的方式找到满足至少窃取 `k` 间房屋的最小窃取能力。

时间复杂度: O(n log(max(nums) - min(nums)))

空间复杂度: O(1)

def least_houses(nums, cap):
    \"\"\" 计算在不超过cap能力下可以窃取的最多房屋数 \"\"\"
    count, visited = 0, False
    for x in nums:
        if x <= cap and not visited:
            count, visited = count + 1, True
        else:
            visited = False
    return count


def house_robber_iv_binary_greedy(nums, k):
    start, end = min(nums), max(nums)
    least = 0
    while start <= end:
        middle = (start + end) // 2
        res = least_houses(nums, middle)
        if res >= k:
            least = middle
            end = middle - 1
        else:
            start = middle + 1
    return least


class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        return house_robber_iv_binary_greedy(nums, k)

Explore

在题解中，二分查找的上下界确定为数组中的最小值和最大值，是基于这样的考虑：最小窃取能力不可能低于数组中的最小值，因为小偷至少需要有能力窃取最容易窃取的房屋；同时，最大窃取能力设为数组中的最大值是因为，如果小偷的能力高于所有房屋的价值，那么他可以选择窃取任何房屋。因此，这样设置上下界可以确保涵盖所有可能的窃取能力，从而找到满足条件的最小能力。

贪心算法在这个题解中的应用体现在每次选择窃取的房屋上。在 `least_houses` 函数中，贪心策略是尽可能多地窃取房屋。具体实现是，遍历房屋列表，每当遇到一个房屋的价值不超过小偷的当前能力且前一个房屋没有被窃取时，就选择窃取这个房屋。这种方法尝试最大化在给定能力下能窃取的房屋数量，以此来满足至少窃取 `k` 间房屋的目标。

`visited` 变量在 `least_houses` 函数中用来标记前一个房屋是否被窃取。这是因为题目可能含有隐含的规则，比如小偷不能连续窃取两间相邻的房屋（虽然题目描述中没有明确说明这一点，这里是一个假设）。使用 `visited` 变量可以帮助确保在选择窃取下一个房屋时，不违反这一规则。如果没有这个变量，我们无法记录上一间房屋的窃取状态，从而可能导致选择了不合规的窃取策略。

`least_houses` 函数通过遍历房屋数组 `nums` 来计算在不超过给定能力 `cap` 下可以窃取的最多房屋数。在遍历过程中，如果遇到一个房屋的价值超过 `cap`，则小偷不能窃取这个房屋。此时，`visited` 变量会被设置为 `False`，表示当前房屋未被窃取，这也为可能的下一个可窃取的房屋重置了状态。如果房屋的价值不超过 `cap` 且前一个房屋没有被窃取（`visited` 为 `False`），则小偷会窃取该房屋，`visited` 会设置为 `True`。这样的逻辑保证了在不超过小偷能力的前提下尽可能多地选择窃取房屋。