刷算法题刷到第807题时我第一反应是“保持城市天际线”这个名字太像城市管理部门的工作总结。题目本身却意外地干净利落给你一个二维矩阵每个数字是一栋建筑的层数允许你把任意建筑加高但加完之后从东、南、西、北四个方向看过去的天际线必须和原来完全一样最后求最多能增加的总层数。我第一次读题时也被“四个方向”绕了一下总觉得要准备四份几何轮廓去做匹配。真正动手推导才发现四个方向压缩到最后只有两个数组每一行的最高值和每一列的最高值。只要把这两个数组算出来整道题的答案几乎就写在纸面上了。这篇我就从翻译题意开始把证明、代码、边界用例和复杂度全部拆开讲一遍最后再说两句我在这道题上踩过的坑。1. 读懂“天际线”行最大值和列最大值到底约束着什么1.1 从南北看天空线就是每一列的最高楼先做一个思维实验。你站在一块网格的正北方向视线贴着地面往南看这时候你真正看到的是一列楼的侧面剪影。剪影的形状并不取决于每一栋楼的具体高度而是取决于这一列里最高那栋楼。只要这一列的最高值不变哪怕把其他楼统统补到和最高楼一样高从南北方向看过去轮廓依然是老样子。同理你从正南方向往北看看到的还是同一组列最大值。所以“南看”和“北看”其实共享同一份数据它们只对应一个数组列最大数组 C。很多资料会把四个方向说得很玄仿佛要做四次不同方向的扫描实际上矩阵是离散的、规则排列的南北方向就是逐列取最大值。1.2 从东西看每一行的最高楼决定轮廓再看左右两个方向。站在第 i 行的最左侧往右看视野范围内最显眼的轮廓线由这一行的最大值决定站在最右侧往左看得到的是同一组行最大值。因此“东看”和“西看”也只需要一份数据行最大数组 R。到这里题目已经从“保持城市天际线”化简成了非常具体的约束加高任意格子但不能改变它所在行的最大值也不能改变它所在列的最大值。后文所有推导都建立在这个化简之上。有一个很容易犯的理解误区有人会把天际线想成“所有建筑顶点的连线”然后试图去比较折线形状。题目里的模型不用那么复杂因为输入输出都是离散高度轮廓的唯一信息就是每行每列的最大值。换句话说只要保证每个格子的新高度同时不超过原行最大值和原列最大值天际线就保住了一旦有某个格子突破其中一个最大值相应的那一侧轮廓立刻改变。这个化简也是整道题的核心认知节点。后续的公式、代码、证明全部围绕“两个方向各给一组合法上界”展开。2. 上限推导为什么是 min(行最大值, 列最大值)2.1 从“方向约束重叠”到“取小”现在把任意一个格子孤立出来看。它在第 i 行行最大值是 R[i]它在第 j 列列最大值是 C[j]。如果加高后这个格子的高度超过 R[i]那么第 i 行从左右看过去的轮廓就会改变违反东西方向的约束如果超过 C[j]第 j 列从南北看过去的轮廓就会改变违反南北方向的约束。为了同时满足两个方向这个格子最终能达到的最大高度必须同时小于等于 R[i] 和 C[j]。两个不等式同时成立等价于新高度 H[i][j] ≤ min(R[i], C[j])。这就是那个关键 min 的由来。它不是一个凭空背下来的公式而是把行方向约束和列方向约束取交集的自然结果。生活里可以这么类比你同时向两个部门申请加高许可行方向部门批的额度是 R[i]列方向部门批的额度是 C[j]最终能批下来的就是两个额度里较小的那个。2.2 上界是否真的够得到只证明 min(R[i], C[j]) 是上界还不够还需要说明每个格子都能真的加到这一高度并且城市天际线一变都不变。否则这可能只是一个理论极限无法作为可执行方案。设新高度矩阵为 HH[i][j] min(R[i], C[j])。先检查第 i 行的轮廓因为原矩阵第 i 行里必然存在一个位置 k使得原来的 grid[i][k] R[i]也就是说第 i 行原本的“最高楼”在 k 列。这个位置的新高度是 min(R[i], C[k])。注意既然 grid[i][k] R[i]那么它所在的第 k 列的列最大值 C[k] 一定不小于 R[i]。所以 min(R[i], C[k]) 实际上等于 R[i]。换句话说原行最高楼在新方案里依然保持 R[i] 的高度其他格子的新高度又都小于等于 R[i]因此整行最大值还是 R[i]东西方向的轮廓没有变。再按同样的逻辑看任意一列也能找到对应的原列最高楼它在新方案里高度保持 C[j]南北方向的轮廓同样不变。两个方向都验证完毕H 确实是一组合法的新高度。2.3 为什么所有格子可以同时加到上限还有一个容易忽略的问题增高某一个格子之后会不会导致其他格子的“合法上限”发生变化比如第一行第一列本来可以加到5结果第一行第二列先加高了第一行的天际线会不会被撑高从而反过来压缩第一行其他格子的空间。这道题不会出现这种情况因为所有合法高度的上限都以原始矩阵的 R 和 C 为基准而原始矩阵从推断出来那一刻就不再改变。每个格子是否达到上限只取决于它自己所在行和列的原始最大值与邻居的最后高度无关。既然每个格子的操作相互独立最优策略就是把每个格子都顶到 min(R[i], C[j])。任何一个格子少加一点总量就会变少所以在所有合法的新高度矩阵里H 的总和最大。由此答案就是最大增加高度总和 所有格子的 min(R[i], C[j]) - grid[i][j] 之和。3. 代码落地先扫后算和扫描合并的两种写法3.1 Python 版先把两个最大值数组算出来我提交时用的是最直观的两阶段写法代码分成“求最大值数组”和“二次求和”两步阅读性最好。class Solution: def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) - int: n len(grid) row_max [max(row) for row in grid] col_max [] for j in range(n): col_max.append(max(grid[i][j] for i in range(n))) ans 0 for i in range(n): for j in range(n): ans min(row_max[i], col_max[j]) - grid[i][j] return ans这段代码没有任何魔法。第一步算行最大直接用内置 max 一行搞定第二步算列最大时注意这里要按列去扫描 grid用生成器表达式取 grid[i][j]。最后求和的时候每个格子的增量就是公式原样翻译。这里要提醒一个 Python 新手容易踩的坑不要把 col_max 初始化和 row_max 共享同一个列表对象例如col_max row_max。Python 里这会让两个变量指向同一个列表后续更新 col_max 时会连带改变 row_max最终答案完全错误。保险做法是独立创建两个列表。3.2 C 版一次双循环同时算出两组最大值C 里我更习惯在一次双层循环里同时更新行最大值和列最大值因为矩阵在这里就是二维数组顺手就能做掉不需要像 Python 那样为列方向单独写生成器。class Solution { public: int maxIncreaseKeepingSkyline(vectorvectorint grid) { int n grid.size(); vectorint rowMax(n, 0), colMax(n, 0); for (int i 0; i n; i) { for (int j 0; j n; j) { rowMax[i] max(rowMax[i], grid[i][j]); colMax[j] max(colMax[j], grid[i][j]); } } int ans 0; for (int i 0; i n; i) { for (int j 0; j n; j) { ans min(rowMax[i], colMax[j]) - grid[i][j]; } } return ans; } };这段代码在遍历到格子 grid[i][j] 时同时用它的高度去更新自己所在行的最大值和自己所在列的最大值。因为rowMax[i]只看第 i 行colMax[j]只看第 j 列所以两个更新互不干扰。之后所有行最大值和列最大值都准备完毕再用完全相同的方式求增量总和。如果你觉得只扫描一遍更舒服可以把“求最大值”和“统计增量”合并到一次双重循环里吗答案是不行。因为第二遍统计增量时需要完整的 R 和 C必须等第一遍全部扫完才知道。这也是这道题时间复杂度虽然 O(n²)但常数上是两到三次遍历的原因。3.3 矩形网格怎么办题面上说 grid 是 n×n但实际思路对 n×m 的矩形同样成立。只要把行最大数组长度设为行数把列最大数组长度设为列数即可。def max_increase_for_rect(grid): rows len(grid) cols len(grid[0]) row_max [max(grid[i]) for i in range(rows)] col_max [max(grid[i][j] for i in range(rows)) for j in range(cols)] total 0 for i in range(rows): for j in range(cols): total min(row_max[i], col_max[j]) - grid[i][j] return total非方阵情况下的分析完全一样行方向约束和列方向约束各自独立没有因为矩形而多出任何新限制。4. 边界试验最小尺寸、全零、全相同这些退化输入到底会怎样4.1 用题面给的矩阵手算一遍先用题面自带的 4×4 矩阵手动验证公式。原矩阵为3 0 8 4 2 4 5 7 9 2 6 3 0 3 1 0行最大值是 8、7、9、3列最大值是 9、4、8、7。逐个格子算 min(行最大, 列最大) 与原始高度的差四行加起来分别是 13、7、9、8总和是 37。这和题目示例完全一致说明我们推导出的公式不是空谈。这里有个细节第一行第一列的 3 虽然被提升到 min(8,9)8第一行第三列原本就已经是 8继续提升到 min(8,8)8零增量。一行里不是所有格子都要提升只有那些离自己的“交叉上限”还有差距的格子才会贡献增量。4.2 全零数组和全相同数组如果整个城市所有建筑高度都是 0那么每一行最大值和每一列最大值自然都是 0。任意格子的 new 高度是 min(0,0)0增量恒为 0。全部建筑都是同一高度 a 时也一样行最大值和列最大值都是 a任意格子 min(a,a)a原始高度已经是 a增量又是 0。这类退化输入最容易让我想到一个问题做题时不要凭借“有建筑就会增加”的直觉提交要确认每一个格子确实存在提升空间。只有当你所在行和所在列里有比当前这个格子更高的建筑时当前格子才有被填补的可能性。4.3 单元素矩阵和对角线矩阵n1 时只有一个格子的城市完全动弹不得。行最大值就是它自己列最大值也是它自己min 之后还是原高度结果毫无疑问是 0。更有意思的测试用例是一个对角线形矩阵比如4 0 0 0 4 0 0 0 4三行最大值全是 4三列最大值也全是 4。也就是说中间那些 0 高度格子的合法上限都是 4。最终整座城市会变成所有格子高度都等于 4 的均匀网格增量是 24。但注意改造后天际线并没有变从南北方向看过去每一列的最高值仍是 4从东西方向看过去每一行的最高值也仍是 4。这个例子能帮你快速识别自己的实现是否真的遵循“只保最大值不保具体分布”的题意。如果代码输出 24并且能解释清楚为什么变成了均匀网格那你对这道题的理解就比较扎实了。5. 复杂度复盘O(n²) 的时间O(n) 的空间到底还能不能省5.1 时间下界至少要把每个格子看一遍题目要返回总和而每个格子的高度都参与计算。哪怕只求行最大值和列最大值也必须把每个格子至少访问一次所以时间复杂度下界是 O(n²)。三次 O(n²) 级别的遍历不会改变量级。如果从实际运行角度考虑n 通常非常小经典题目的 n 不超过 50即使直接写三重循环也未必超时。但作为算法练习我们还是应该追求常数可控的两遍或三遍扫描版本而不是在每算一个格子时都把整行整列重新求一遍最大值。5.2 空间上R 和 C 两个数组已经是常规最优空间占用来自两个数组一个长度 n 的 row_max一个长度 n 的 col_max所以是 O(n)。相比整个矩阵 O(n²)这已经很轻量。有人会问能不能做到 O(1) 额外空间把行最大值和列最大值直接“压”在原始矩阵的某一行某一列里实践上很麻烦因为你一旦覆盖了原始高度后面计算每个格子的增量时原值已经丢失。而不覆盖原始值又想保存两个长度均为 n 的最大值数组O(n) 的空间就是必要开销。与其设计绕来绕去的原地压缩不如直接使用两个数组可读性和正确性都更可靠。下面的表可以更直观地概括常见写法做法时间额外空间说明行最大值和列最大值各扫一遍再求和O(n²)O(n)最简单推荐一次双层循环同时更新 R 和 C再求和O(n²)O(n)C 里更顺手每算一个格子都重新求行最大值和列最大值O(n³)O(1)一个典型的糟糕实现最后一种实现虽然空间更小但时间退化到立方级在小数据上还能跑一旦矩阵变大就会明显吃力。它不值得学。5.3 复杂度结论复杂度分析给我们的核心结论是只要需要保存每组最大值O(n) 的额外空间不可避免而时间上因为要读完整张矩阵O(n²) 是最小可行下界。明白这一点后再去优化代码时就不会把精力浪费在幻想 O(n) 时间和 O(1) 空间上了。6. 同类题目与方法论沉淀这道题给我留下的三个提醒6.1 二维前缀/后缀最大值是矩阵题里的常见套路把“保持城市天际线”往后看这类用行方向和列方向聚合信息解决问题的思路在算法题里出现得非常频繁。比如一维数组里求每个位置能接多少水往往需要预先知道当前位置左侧最大值和右侧最大值再取两者较小者作为水面高度。807 题本质上是在二维网格里复刻了这个“前缀/后缀最大”的思维模式。区别在于一维接雨水问题是左右两个方向各有前缀数组而 807 题是“行”和“列”两个方向。只要识别出“最终限制来自两个正交方向”你就能迅速判断出应该准备哪两个预计算数组。6.2 多个约束叠加时直接取交集往往就是最优解这道题另一个值得记住的抽象是当一个决策同时受多个独立上限约束时合法范围是所有约束的交集最大值自然是交集的边界。行给一个上限列给一个上限取 min如果换成行给下限、列给上限就要用更复杂的区间相交去讨论。这类“约束交集”的思维在区间调度、匹配问题、资源分配里都会反复出现。刷题时积累的不是“807 题答案是 37”而是“我如何从多方向约束里提取出独立的聚合值再对它们取交集”。6.3 刷题时值得养成的验证习惯我实际做题时常用一个 2×2 的小用例快速验证公式。比如1 2 3 4行最大值是 2 和 4列最大值是 3 和 4。四个格子的增量分别是 1、0、0、0总和是 1。这个用例虽然小却能同时覆盖行约束生效、列约束生效、最大值格子零增量三种情况。提交前在心里跑一遍这种 2×2 用例能过滤掉绝大多数因为数组维度、方向写反导致的低级错误。我还遇到过一次比较隐蔽的错误在 Python 里不小心把两个最大值列表指向了同一个对象导致修改第二组时第一组也跟着变整个答案完全失控。从那以后凡是用到两个平行数组我都会先确认它们的初始化是否完全独立。最后分享一点个人体会刷完这道题我最深的感受不是“我记住了 min(R[i], C[j]) 这个公式”而是学会了遇到“从某个方向看轮廓不变”的描述时先问自己一句这个方向化简后真正参与判断的聚合指标到底是什么答案一旦落到行最大、列最大这类具体数据上剩下的事情就只是把约束翻译成代码了。