题目描述
思路解析动画文字版
记住这个套路:每个格子填的是当前这一行余额和这一列余额里较小的那个,填完两边一起扣。为什么取较小值,因为填多了某一边就会超额变成负数。下面咱们从左上角开始,一格一格地填。
开局 · 空矩阵 + 行列余额：这是一个 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题