题目描述
思路解析
一句话答案：LeetCode 1605 给定行和列的和求可行矩阵：逐格填行余额与列余额里较小的那个、填完从两边同减，一遍贪心构造就凑出一个合法解，时间 O(m·n)、空间 O(1)。
只知道每行每列的和，怎么倒推出矩阵
给两个非负整数数组 rowSum 和 colSum,rowSum[i] 是矩阵第 i 行之和，colSum[j] 是第 j 列之和。要造一个 rowSum.length 行、colSum.length 列的非负整数矩阵，让每行、每列的和都对上。题目保证有解，返回任意一个即可。题面例子 rowSum=[5,7,10]、colSum=[8,6,8]，答案之一是 [[5,0,0],[3,4,0],[0,2,8]]。
看到行列和就想列方程组，方程却不够用
3 行 3 列的矩阵有 9 个未知数，行和列却只给了 6 个方程，方程比未知数少、解本就不唯一，这也是题目允许『返回任意一个』的原因。真去列方程组反推没必要：行、列的和各自只约束自己那一维，自由度很大。只要一个合法解，顺着一格格填就能凑出来。
每格该填多大，取行列余额里的较小值
填每格前盯住两个数：这一行还差多少，记成行余额；这一列还差多少，记成列余额。这格填的数不能超过行余额、也不能超过列余额，否则对应的行或列就超标。两个上限取小的那个，就是这格能安全填下的最大值。所以每格填 min(行余额，列余额)。填成较大的那个，余额小的一边会被扣成负数，破坏非负约束。
填完一个数，行和列两笔账都要扣
定下这格填 x 后，把 x 从行余额和列余额里同时减掉。按行优先，从左上角起往右、填满一行再下一行，每到一格算 min、填进去、两边同减。哪边余额先归 0，那一行或那一列剩下的只能填 0。最常见的写错是只扣了行余额、忘了扣列余额：列余额虚高一截，后面接着按错的数填，整张表就全乱。
[5,7,10] 配 [8,6,8]，逐格填一遍
起手行余额 [5,7,10]、列余额 [8,6,8]。(0,0) min(5,8)=5，行余额转 [0,7,10]、列余额转 [3,6,8];(0,1) min(0,6)=0;(0,2) min(0,8)=0，第 0 行 [5,0,0]。
第 1 行：(1,0) min(7,3)=3，行余额转 [0,4,10]、列余额转 [0,6,8];(1,1) min(4,6)=4;(1,2) min(0,8)=0，得 [3,4,0]。第 2 行：(2,0) min(10,0)=0;(2,1) min(10,2)=2;(2,2) min(8,8)=8，两边同时归 0，得 [0,2,8]。拼起来是 [[5,0,0],[3,4,0],[0,2,8]]，每行和 5、7、10、每列和 8、6、8，正是题面两组数。
min 写成 max，整张表当场垮掉
最伤的错是把 min 写成 max、想多填：填成较大的那个，余额小的一边直接扣成负数，非负约束跟着破。另一个顾虑是怕填到右下角两边余额对不上；但题目保证行总和等于列总和，每格都从两边扣掉相同的数，两组余额总和始终相等，填到最后一格必然恰好相等、同时归 0。
复杂度上，双重循环把每个格子恰好访问一次，每格取较小值加两次减法都是常数，时间 O(m·n)；除答案矩阵外只多用一个临时变量，空间 O(1)。两个边界也想清：只有一格时直接填两边较小值；某行的和一开始就是 0，整行填 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这个套路:每个格子填的是当前这一行余额和这一列余额里较小的那个,填完两边一起扣。为什么取较小值,因为填多了某一边就会超额变成负数。下面咱们从左上角开始,一格一格地填。
开局 · 空矩阵 + 行列余额：这是一个 3 行 3 列的空矩阵,所有格子先用点号占位表示还没决定。右边面板上一排是每一行还差多少,现在是 5、7、10;下一排是每一列还差多少,现在是 8、6、8。注意这两排数字加起来都是 22,是相等的,这一点等会儿到最后一格会派上大用场。咱们从左上角第 0 行第 0 列开始填。
看 (0,0) · 行余 5 , 列余 8：来到格子第 0 行第 0 列。这一行只差 5,这一列还差 8,这一行余额更少,取较小值 5。要是填得比 5 还多,这一行就超额了,所以最多填 5。
填 (0,0) = 5：把 5 填进第 0 行第 0 列。填完之后,这一行余额从 5 变成 0,这一行后面的格子就只能填 0 了;这一列还差 3。
看 (0,1) · 行余 0 , 列余 6：来到格子第 0 行第 1 列。这一行只差 0,这一列还差 6,这一行余额更少,取较小值 0。要是填得比 0 还多,这一行就超额了,所以最多填 0。
填 (0,1) = 0：把 0 填进第 0 行第 1 列。填完之后,这一行余额从 0 变成 0,这一行后面的格子就只能填 0 了;这一列还差 6。
看 (0,2) · 行余 0 , 列余 8：来到格子第 0 行第 2 列。这一行只差 0,这一列还差 8,这一行余额更少,取较小值 0。要是填得比 0 还多,这一行就超额了,所以最多填 0。
填 (0,2) = 0：把 0 填进第 0 行第 2 列。填完之后,这一行余额从 0 变成 0,这一行后面的格子就只能填 0 了;这一列还差 8。
第 0 行填完 · [5, 0, 0]：第 0 行填完了,内容是 5、0、0,加起来是 5,正好等于 rowSum 给的 5,这一行的余额已经归 0。接着填第 1 行。
看 (1,0) · 行余 7 , 列余 3：来到格子第 1 行第 0 列。这一行还差 7,这一列只差 3,这一列余额更少,取较小值 3。填多了这一列就会超额,所以这一格填 3。
填 (1,0) = 3：把 3 填进第 1 行第 0 列。填完之后,这一列余额从 3 变成 0,这一列后面的格子也只能填 0;这一行还差 4。
看 (1,1) · 行余 4 , 列余 6：来到格子第 1 行第 1 列。这一行只差 4,这一列还差 6,这一行余额更少,取较小值 4。要是填得比 4 还多,这一行就超额了,所以最多填 4。
填 (1,1) = 4：把 4 填进第 1 行第 1 列。填完之后,这一行余额从 4 变成 0,这一行后面的格子就只能填 0 了;这一列还差 2。
看 (1,2) · 行余 0 , 列余 8：来到格子第 1 行第 2 列。这一行只差 0,这一列还差 8,这一行余额更少,取较小值 0。要是填得比 0 还多,这一行就超额了,所以最多填 0。
填 (1,2) = 0：把 0 填进第 1 行第 2 列。填完之后,这一行余额从 0 变成 0,这一行后面的格子就只能填 0 了;这一列还差 8。
第 1 行填完 · [3, 4, 0]：第 1 行填完了,内容是 3、4、0,加起来是 7,正好等于 rowSum 给的 7,这一行的余额已经归 0。接着填第 2 行。
看 (2,0) · 行余 10 , 列余 0：来到格子第 2 行第 0 列。这一行还差 10,这一列只差 0,这一列余额更少,取较小值 0。这一列其实已经填够了,余额是 0,那这一格只能填 0。
填 (2,0) = 0：把 0 填进第 2 行第 0 列。填完之后,这一列余额从 0 变成 0,这一列后面的格子也只能填 0;这一行还差 10。
看 (2,1) · 行余 10 , 列余 2：来到格子第 2 行第 1 列。这一行还差 10,这一列只差 2,这一列余额更少,取较小值 2。填多了这一列就会超额,所以这一格填 2。
填 (2,1) = 2：把 2 填进第 2 行第 1 列。填完之后,这一列余额从 2 变成 0,这一列后面的格子也只能填 0;这一行还差 8。
看 (2,2) · 行余 8 , 列余 8：来到格子第 2 行第 2 列。这一行还差 8,这一列也还差 8,两边一样大,取较小值就是 8,准备把 8 填进去。
填 (2,2) = 8：把 8 填进第 2 行第 2 列。填完之后,这一行余额归 0,这一列余额也归 0,两边同时填满了。
第 2 行填完 · [0, 2, 8]：第 2 行填完了,内容是 0、2、8,加起来是 10,正好等于 rowSum 给的 10,这一行的余额已经归 0。所有格子都填完了,来看最终结果。
答案 · 整个矩阵填好：整个矩阵填好了,是 5、0、0,3、4、0,0、2、8。验一下,每一行加起来是 5、7、10,跟 rowSum 完全一样;每一列加起来是 8、6、8,跟 colSum 也完全一样,所有数字都非负。最关键的是最右下角那一格,当时这一行还差 8、这一列也正好差 8,因为行总和等于列总和,前面每一步又都从两边扣掉相同的数,所以收尾这一格两边余额必然相等,稳稳填上 8 收官。
边界想清:单格直接填两边较小值、某行余额一开始就是 0 时整行填 0、任意尺寸都按行优先逐格取较小值填。
面试重点:用「不出负数加总和相等」证明贪心可行、填格顺序可以任意、它本质是运输问题的西北角法构造初始可行解。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]: m, n = len(rowSum), len(colSum) ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): x = min(rowSum[i], colSum[j]) ans[i][j] = x rowSum[i] -= x colSum[j] -= x return ans复杂度
- 时间：O(m·n)，m 是行数,n 是列数。整个算法就是一个双重循环把每个格子访问恰好一次,每个格子里做的取较小值和两次减法都是常数时间,所以总时间就是格子总数 m 乘 n
- 空间：O(1)，除了那张必须返回的 m 乘 n 答案矩阵之外,只用了 x 这一个临时变量和两个循环下标,没有额外随规模增长的辅助空间。返回矩阵是题目要求的输出,不计入额外空间,所以额外空间按峰值是常数 O(1)
易错点
面试追问把动画讲成自己的话
追问怎么证明这个贪心一定能填出合法矩阵,不会卡住或出负数?
追问填的顺序必须是行优先吗,换个顺序行不行?
追问这道题和运筹学或者图论里的什么模型有关系吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大网络秩
LeetCode 1615 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题