Medium

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是相邻的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷盗到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

输入：nums = [1,2,3]
输出：3

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

解题思路

这是经典的"打家劫舍"问题的变形。关键在于房屋围成一圈，第一间房和最后一间房相邻。

核心思路： 由于第一间房和最后一间房相邻，我们不能同时选择它们。因此可以分为两种情况：

  1. 偷第一间房，则不能偷最后一间房（对 nums[0...n-2] 求解）
  2. 偷最后一间房，则不能偷第一间房（对 nums[1...n-1] 求解）

取两种情况的最大值即为答案。

算法步骤：

  1. 特殊情况：如果只有1间房，直接返回该房的金额
  2. 定义辅助函数 robLinear，解决线性排列的打家劫舍问题（经典动态规划）
  3. 分别计算两种情况的最优值：
    • 情况1：包含第一间房，排除最后一间房
    • 情况2：排除第一间房，包含最后一间房
  4. 返回两种情况的最大值

对于线性情况，使用动态规划：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，表示到第i间房时的最大收益。为节省空间，只用两个变量记录前两个状态。

代码实现

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        
        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }
    
private:
    int robLinear(vector<int>& nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int curr = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        return max(self.rob_linear(nums, 0, n - 2), self.rob_linear(nums, 1, n - 1))
    
    def rob_linear(self, nums, start, end):
        prev2, prev1 = 0, 0
        for i in range(start, end + 1):
            curr = max(prev1, prev2 + nums[i])
            prev2, prev1 = prev1, curr
        return prev1

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 1) return nums[0];
        
        return Math.Max(RobLinear(nums, 0, n - 2), RobLinear(nums, 1, n - 1));
    }
    
    private int RobLinear(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int curr = Math.Max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 1) return nums[0];
    if (nums.length === 2) return Math.max(nums[0], nums[1]);
    
    const robLinear = (houses) => {
        let prev2 = 0, prev1 = 0;
        for (let house of houses) {
            let curr = Math.max(prev1, prev2 + house);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    };
    
    return Math.max(
        robLinear(nums.slice(0, -1)),
        robLinear(nums.slice(1))
    );
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次O(n)
空间复杂度O(1)只使用常数个额外变量

相关题目