矩阵置零

Matrix City · 污染隔离

别急着清零：先保存「原始污染源」的行列信息

矩阵模拟原地标记信息污染O(1) 空间

输入矩阵

时间复杂度

O(mn)

额外空间

O(1)

目标输出：[[1,0,1],[0,0,0],[1,0,1]]

每个格子是一栋楼，0 是污染源。正确策略是第一轮只贴标记（哪些行/列要封锁），第二轮再统一清零。第一行第一列是矩阵自带的公告栏，用 O(1) 空间替代 rowMark/colMark 数组。

速度Step 1/21 · 题目规则

题目规则：发现一个原始 0，封锁整行整列

矩阵城市里，每个格子是一栋楼。数字 0 代表污染源——一旦发现，它所在的整行和整列都要封锁为 0。

输入 [[1,1,1],[1,0,1],[1,1,1]]。中心 (1,1) 是唯一的原始污染源。目标输出 [[1,0,1],[0,0,0],[1,0,1]]。

为什么这样做

先把规则讲清楚：我们只对「原本就是 0」的格子扩散，不是对任意 0 都扩散。

目标结果

矩阵城市 · 污染隔离区

3×3

原始 0制造的 0标记 0封锁 0首行/首列 = 公告栏

(0,0)1

(0,1)1

(0,2)1

(1,0)1

(1,1)0原始污染源

(1,2)1

(2,0)1

(2,1)1

(2,2)1

Go · 逐行高亮

setZeroes(matrix)

1func setZeroes(matrix [][]int) {
2    m, n := len(matrix), len(matrix[0])
3 
4    firstRowZero := false
5    firstColZero := false
6 
7    for j := 0; j < n; j++ {
8        if matrix[0][j] == 0 {
9            firstRowZero = true
10            break
11        }
12    }
13 
14    for i := 0; i < m; i++ {
15        if matrix[i][0] == 0 {
16            firstColZero = true
17            break
18        }
19    }
20 
21    for i := 1; i < m; i++ {
22        for j := 1; j < n; j++ {
23            if matrix[i][j] == 0 {
24                matrix[i][0] = 0
25                matrix[0][j] = 0
26            }
27        }
28    }
29 
30    for i := 1; i < m; i++ {
31        for j := 1; j < n; j++ {
32            if matrix[i][0] == 0 || matrix[0][j] == 0 {
33                matrix[i][j] = 0
34            }
35        }
36    }
37 
38    if firstRowZero {
39        for j := 0; j < n; j++ {
40            matrix[0][j] = 0
41        }
42    }
43 
44    if firstColZero {
45        for i := 0; i < m; i++ {
46            matrix[i][0] = 0
47        }
48    }
49}

执行轨迹

i: —
j: —
firstRowZero: —
firstColZero: —
当前动作: 阅读题目：识别原始污染源 (1,1)
当前不变量: 尚未修改矩阵；只标记原始 0 的位置。

这题的不变量

第一遍扫描内部区域之后：matrix[i][0] == 0 表示第 i 行最终需要清零；matrix[0][j] == 0 表示第 j 列最终需要清零。
applyMarkers 阶段：每个内部格子是否清零，只由它所在行/列的标记决定。
第一行第一列必须最后处理：因为它们在算法过程中承担标记存储功能。

当前步仍成立：尚未修改矩阵；只标记原始 0 的位置。

三个最容易错的点

错误 1：边扫描边清零
会把新制造的 0 当成原始 0，后续扫描会误判扩散范围。
错误 2：忘记 firstRowZero / firstColZero
第一行第一列被复用成标记区后，它们自己原本是否需要清零的信息会丢失。
错误 3：太早清零第一行第一列
会破坏标记公告栏，导致内部区域 apply 阶段判断错误。

复杂度

时间 O(mn)：四轮扫描（保存边界、写标记、apply、finalize），每轮最多遍历全部格子。
额外空间 O(1)：只用 firstRowZero / firstColZero 两个变量，公告栏复用矩阵首行首列。

步骤轨迹

#	阶段	说明	动作
1	题目规则	题目规则：发现一个原始 0，封锁整行整列	阅读题目：识别原始污染源 (1,1)
2	错误做法	错误做法：巡逻机器人边扫边封锁	扫描到 (1,1)，准备立即封锁行列
3	错误做法	立刻封锁后：新出现的 0 不是原始污染源	继续扫描 → 高亮「刚制造的 0」
4	错误做法	结论：先记录，再统一执行	放弃边扫边改 → 进入正确方案
5	额外数组	朴素正确方案：用额外数组记录行列	第一遍扫描：只写 rowMark / colMark
6	额外数组	第二遍：按标记统一清零	第二遍扫描：按 rowMark/colMark 清零
7	保存边界	O(1) 关键：第一行第一列是公告栏	检查第一行是否有原始 0 → firstRowZero
8	保存边界	firstRowZero = false，继续检查第一列	检查第一列是否有原始 0 → firstColZero
9	保存边界	matrix[0][0] 是冲突路口	firstRowZero=false · firstColZero=false · 保存完毕
10	写标记	扫描内部 (1,1)	发现 0 → 准备写 matrix[1][0] 和 matrix[0][1]
11	写标记	写入标记：第 1 行 · 第 1 列	matrix[1][0]=0 · matrix[0][1]=0
12	写标记	扫描内部 (1,2)	matrix[1][2] != 0，跳过
13	写标记	扫描内部 (2,1)	matrix[2][1] != 0，跳过
14	写标记	扫描内部 (2,2)	matrix[2][2] != 0，跳过
15	写标记	标记完成：公告栏已记录行列需求	标记阶段完成，准备 apply
16	统一清零	apply 内部 (1,1)：查公告栏	matrix[1][1] = 0
17	统一清零	apply 内部 (1,2)：查公告栏	matrix[1][2] = 0
18	统一清零	apply 内部 (2,1)：查公告栏	matrix[2][1] = 0
19	统一清零	apply 内部 (2,2)：查公告栏	matrix[2][2] 保持 1
20	最后处理	最后处理第一行和第一列	firstRowZero=false → 跳过 · firstColZero=false → 跳过
21	最后处理	完成：最终输出	算法完成

面试一句话

用第一行第一列当 O(1) 标记区：先保存边界原始 0 状态到 firstRowZero/firstColZero，再扫描内部写标记、按标记清零内部，最后处理边界。时间 O(mn)，空间 O(1)。