跳转至

213. 打家劫舍 II（House Robber II）

频次 ★★★★ · 难度 🟡 · 高频：美团

题目

198 进阶版——房屋首尾相连成环。

示例： 

输入: nums = [2,3,2]
输出: 3  （偷第一家或第三家，不能同时偷因为首尾相邻）

思路

环形拆成两个线性问题：因为首尾互斥，只需要分别求"去掉尾"和"去掉头"的两个线性打家劫舍，取最大值。

  • robRange(nums, 0, n-2)：偷第一家，不偷最后一家
  • robRange(nums, 1, n-1)：不偷第一家，偷最后一家
  • 取两趟的 max

代码

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}

private int robRange(int[] nums, int l, int r) {
    int prev2 = 0, prev1 = 0;
    for (int i = l; i <= r; i++) {
        int cur = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

环形拆解与区间合同（实测复盘）

首尾互斥 → 全方案按"首偷/首不偷"二分两世界：
  A=robRange(0, n-2)  B=robRange(1, n-1)   n=1 特判（自己≠自己邻居）
198 公式参数化为 robRange(l, r) 工具——"复用而不重写递推"是工程要义
  • n=1 哨兵：单栋返 nums[0]（位掩码参考自己算自己邻居的教训——环的自己≠邻居）
  • 区间合同二分：甲=闭区间 i<=r（配首尾真下标 n-2/n-1）；乙=半开 i<r（配 n-1/n，空区间 l==r 有自然写法、与 Java 标准库同频道）——比较符必须匹配调用合同（377 错题本已校准此句）
  • 滚动地基 prev=0 的语义="区间外未偷"——天然覆盖"区间只有一栋/空"的退化情形（与 dp[0] 前缀语义课同源）
  • 198 例2 [2,7,9,3,1] 环形后掉到 11（2+9 vs 7+3）——环比线性必不赚（禁令更紧）

复杂度

  • 时间：O(n)
  • 空间：O(1)

边界条件

  • n = 1：直接返回（环只有一间房屋）
  • n = 2：取 max（两间只能偷一间）

变式

易错点

  • n == 1 需要特判——如果直接进 robRange 两趟会返回错误结果
  • robRange 是左闭右闭区间，包含 r

面试追问

  • 环形约束的本质？ 就是让首尾不能同时选。分两趟是最简单的思路，也可以用状态机 DP 解决（多一个"是否偷第一家"的维度）

关联题