2026-06-12：打家劫舍 V。用go语言，你现在要处理一个“相邻房屋不能同色同时偷”的求最大收益问题： - 有 n 间沿街房屋，第 i 间房屋里

福大大架构师每日一题

发布于 2026-06-12 18:10:05

650

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2026-06-12：打家劫舍 V。用go语言，你现在要处理一个“相邻房屋不能同色同时偷”的求最大收益问题：

• 有 n 间沿街房屋，第 i 间房屋里有 nums[i] 金额。
• 每间房屋还有一个颜色代码 colors[i]。
• 规则是：如果两间房屋相邻（下标 i 和 i+1）且它们的颜色代码相同，那么这两间不能同时被偷。
• 在满足上述限制的前提下，选择要偷的房屋，使得获得的总金额最大。
• 请输出在最优选择下能得到的最大总金额。

1 <= n == nums.length == colors.length <= 100000。

1 <= nums[i], colors[i] <= 100000。

输入： nums = [10,1,3,9], colors = [1,1,1,2]。

输出： 22。

解释：

选择第 i = 0 间房屋（金额为 10）、第 i = 2 间房屋（金额为 3）和第 i = 3 间房屋（金额为 9）。

此选择是合法的，因为第 i = 0 和 i = 2 间房屋不相邻，且第 i = 2 和 i = 3 间房屋颜色不同。

因此，偷窃的总金额为 10 + 3 + 9 = 22。

题目来自力扣3840。

一、逐轮分步演算完整流程（以示例nums=[10,1,3,9]、colors=[1,1,1,2]为例）

初始化阶段（i=0，第一间房屋）

房屋0：金额10，颜色1

• 数组长度不为0，跳过边界返回0逻辑
• f1初始化为0：不偷0号房，收益0
• f2初始化为10：偷0号房，收益10 当前状态：f1=0（不偷0），f2=10（偷0）

第一轮循环：i=1（第二间房屋，金额1，颜色1）

对比相邻颜色：colors[1]=1，colors[0]=1，相邻同色，触发同色分支逻辑。规则：i和i-1同色，不能同时偷i和i-1，因此偷当前i的方案只能来自「不偷i-1的收益f1 + 当前房屋金额」，再和「不偷当前i，保留偷i-1的收益f2」取更大值作为money。

1. 候选1（偷1号房）：f1 + nums[1] = 0 + 1 = 1
2. 候选2（不偷1号房）：f2 = 10
3. 二者取大，money = max(1,10) = 10
4. 滚动更新状态： f1 = 旧f2 = 10（现在f1代表不偷1号房的最大收益） f2 = money = 10（现在f2代表偷1号房的最大收益）本轮结束状态：f1=10，f2=10

第二轮循环：i=2（第三间房屋，金额3，颜色1）

对比相邻颜色：colors[2]=1，colors[1]=1，相邻同色，再次进入同色分支。

1. 候选1（偷2号房）：f1 + nums[2] = 10 + 3 = 13
2. 候选2（不偷2号房）：f2 = 10
3. 二者取大，money = max(13,10) = 13
4. 滚动更新状态： f1 = 旧f2 = 10（不偷2号房最大收益） f2 = money = 13（偷2号房最大收益）本轮结束状态：f1=10，f2=13 解读：此时偷2号房最优收益13，对应方案是不偷1号、偷0号+偷2号（10+3=13），和题目最优方案中间步骤匹配。

第三轮循环：i=3（第四间房屋，金额9，颜色2）

对比相邻颜色：colors[3]=2，colors[2]=1，相邻异色，进入异色分支逻辑。规则：i和i-1颜色不同，无偷窃冲突，可以同时偷i-1和i，因此偷当前i的收益 = 偷i-1的最大收益f2 + 当前房屋金额，直接赋值给money。

1. money = f2 + nums[3] = 13 + 9 = 22
2. 滚动更新状态： f1 = 旧f2 = 13（不偷3号房的最大收益） f2 = money = 22（偷3号房的最大收益）本轮结束状态：f1=13，f2=22

循环结束，返回结果

循环遍历完所有4间房屋，最终f2存储遍历到最后一间房屋、偷最后一间时的全局最大收益，返回22，和题目输出一致。

二、通用算法完整逻辑步骤（脱离示例，通用处理任意n间房屋）

步骤1：边界判断

如果房屋总数n=0，不存在可偷窃房屋，直接返回总收益0。

步骤2：DP状态初始化（处理第0号首间房屋）

• f1：不偷第0间，收益固定为0；
• f2：偷第0间，收益等于第一间房屋金额nums[0]；

步骤3：从第1间到最后一间，依次遍历每一间房屋i（循环i=1 ~ n-1）

每一次循环执行固定三步：

步骤3.1 判断当前i和前一间i-1的颜色关系

分支A：colors[i] != colors[i-1]（相邻异色）相邻异色无偷窃冲突，可以同时偷前一间和当前间。当前房屋偷窃最优收益money = 偷前一间的最大收益f2 + 当前房屋金额nums[i]

分支B：colors[i] == colors[i-1]（相邻同色）相邻同色不能两间都偷，有两种选择：

1. 不偷当前房屋：收益=偷前一间的收益f2；
2. 偷当前房屋：只能不偷前一间，收益=不偷前一间的收益f1 + nums[i]；取两种选择里数值更大的作为money。

步骤3.2 滚动更新DP状态变量

完成money计算后，刷新两个状态变量，为下一间房屋遍历做准备：

1. f1 赋值为原来的f2：下一轮中，f1代表「不偷当前i号房」的最大收益；
2. f2 赋值为本轮算出的money：下一轮中，f2代表「偷当前i号房」的最大收益。

步骤4：遍历全部房屋后输出结果

循环结束后，f2保存的是遍历到最后一间房屋、包含偷最后一间方案的全局最大总金额，直接返回f2作为答案。

三、时间复杂度、额外空间复杂度分析

1. 时间复杂度 O(n)

n为房屋总数，算法仅执行一次单层for循环，循环执行次数恰好n-1次；循环内部仅包含颜色比较、简单四则运算、大小比较，所有操作都是常数时间O(1)；无嵌套循环、无排序、无递归，整体时间复杂度线性O(n)，可以满足题目n≤100000的数据规模。

2. 额外空间复杂度 O(1)

输入的nums、colors属于题目给定输入数组，不计入算法额外空间；算法内部仅永久开辟3个固定变量：f1、f2、money，变量数量不随房屋数量n变化；没有创建DP数组、切片、哈希表等随n扩容的数据结构；仅使用常数级临时存储空间，额外空间复杂度为O(1)。

Go完整代码如下：

package main

import (
    "fmt"
)

func rob(nums []int, colors []int)int64 {
    iflen(nums) == 0 {
        return0
    }
    f1 := int64(0)
    f2 := int64(nums[0])
    n := len(nums)
    for i := 1; i < n; i++ {
        var money int64
        if colors[i] != colors[i-1] {
            money = f2 + int64(nums[i])
        } else {
            if f1+int64(nums[i]) > f2 {
                money = f1 + int64(nums[i])
            } else {
                money = f2
            }
        }
        f1 = f2
        f2 = money
    }
    return f2
}

func main() {
    nums := []int{10, 1, 3, 9}
    colors := []int{1, 1, 1, 2}
    result := rob(nums, colors)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

class Solution:
    def rob(self, nums: List[int], colors: List[int]) -> int:
        iflen(nums) == 0:
            return0
        f1 = 0
        f2 = nums[0]
        n = len(nums)
        for i in range(1, n):
            if colors[i] != colors[i-1]:
                money = f2 + nums[i]
            else:
                money = max(f1 + nums[i], f2)
            f1 = f2
            f2 = money
        return f2


if __name__ == "__main__":
    nums = [10, 1, 3, 9]
    colors = [1, 1, 1, 2]
    result = Solution().rob(nums, colors)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long rob(vector<int>& nums, vector<int>& colors) {
    if (nums.empty()) {
        return0;
    }
    long long f1 = 0;
    long long f2 = nums[0];
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        long long money;
        if (colors[i] != colors[i-1]) {
            money = f2 + nums[i];
        } else {
            money = max(f1 + nums[i], f2);
        }
        f1 = f2;
        f2 = money;
    }
    return f2;
}

int main() {
    vector<int> nums = {10, 1, 3, 9};
    vector<int> colors = {1, 1, 1, 2};
    long long result = rob(nums, colors);
    cout << result << endl;
    return0;
}