What pattern does House Robber IV follow?

It follows state transition dynamic programming combined with binary search to find minimum feasible capability.

How do I check if a candidate capability is valid?

Simulate robbing houses that do not exceed the candidate value using DP-style transitions, ensuring no adjacent houses are robbed, and count successful robberies.

Can this approach handle large nums arrays?

Yes, binary search with linear feasibility check gives O(n log m) time, suitable for up to 105 houses.

Why is binary search needed in House Robber IV?

Binary search efficiently finds the minimum maximum money the robber can take without checking all subsets of houses.

Does the greedy check always guarantee minimum capability?

Yes, when combined with binary search, the greedy feasibility check ensures the lowest maximum value is found while robbing at least k houses.

#2560

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

打家劫舍 IV

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋。小偷的窃取能力定义为他在窃取过程中能从单间房屋中窃取的最大金额。给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上…

数组二分查找动态规划贪心

题目描述

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

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

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

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

lightbulb

解题思路

方法一：二分查找 + 贪心

题目求的是窃贼的最小窃取能力，我们可以二分枚举窃贼的窃取能力，对于枚举的能力 $x$ ，我们可以通过贪心的方式判断窃贼是否能够窃取至少 $k$ 间房屋，具体地，我们从左到右遍历数组，对于当前遍历到的房屋 $i$ ，如果 $nums[i] \leq x$ 且 $i$ 与上一个窃取的房屋的下标之差大于 $1$ ，则窃贼可以窃取房屋 $i$ ，否则窃贼不能窃取房屋 $i$ 。累计窃取的房屋数，如果窃取的房屋数大于等于 $k$ ，则说明窃贼可以窃取至少 $k$ 间房屋，此时窃贼的窃取能力 $x$ 可能是最小的，否则窃贼的窃取能力 $x$ 不是最小的。

时间复杂度 $O(n \times \log m)$ ，空间复杂度 $O(1)$ 。其中 $n$ 和 $m$ 分别是数组 $nums$ 的长度和数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        def f(x):
            cnt, j = 0, -2
            for i, v in enumerate(nums):
                if v > x or i == j + 1:
                    continue
                cnt += 1
                j = i
            return cnt >= k

        return bisect_left(range(max(nums) + 1), True, key=f)

speed

复杂度分析

指标	值
时间	complexity is O(n log m), where n is nums.length and m is the range of money values, due to binary search and linear scan feasibility check. Space complexity is O(1) as we only maintain counters and current state.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate immediately considers binary search combined with DP feasibility check.
question_mark
Explains state transition clearly: rob or skip each house depending on candidate capability.
question_mark
Considers edge cases where k is maximum possible given array length.

warning

常见陷阱

外企场景

error
Failing to enforce non-adjacent house constraint when counting houses for feasibility.
error
Using full DP arrays causing unnecessary O(n) space instead of constant space.
error
Not correctly updating binary search bounds leading to off-by-one errors in minimum capability.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize capability for robbing exactly k houses instead of at least k.
arrow_right_alt
Rob houses with circular adjacency constraint, first and last house considered adjacent.
arrow_right_alt
Rob houses with variable adjacency distances, e.g., at least d houses apart instead of 1.

help

常见问题

外企场景

继续练习

#2616 最小化数对的最大差值 #2439 最小化数组中的最大值 #1671 得到山形数组的最少删除次数