题目描述
思路解析
一句话答案：LeetCode 807 保持城市天际线：每栋楼最高能升到它所在行最大值、列最大值里较小的那个，既不改四个方向的天际线，把每格增量累加就是答案，时间 O(n²)、空间 O(n)。
十六座楼能加多高，还不改四个方向的天际线
给一个 n × n 的高度矩阵 grid，grid[r][c] 是这栋楼的高度。可给任意楼加任意高度，唯一限制是从东、南、西、北四个方向看的天际线都不能变。问所有楼一共最多能加多少。题面例子 grid=[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]，答案 35；矩阵全 0 时谁也加不了，答案 0。
四个方向的天际线，本质就是行最大和列最大
先把『天际线』说清楚：从东西方向望，看到的是每行的最大值；从南北望，看到的是每列的最大值。要真一栋栋加高再重看四个方向，每加一次都得重算整幅，慢得没边。好在天际线只由行最大、列最大这两组数说了算，它们在原矩阵里就定死了。
每格的天花板，为什么是行最大和列最大里较小的那个
盯住第 (i,j) 格：它一旦超过本行最大值，东西向这行天际线就被顶高；超过本列最大值，南北向这列也变。所以它最高只能到本行最大、本列最大里较小的那个，取较大的会顶破较小方向。这个上限就是它的天花板 min(rowMax[i], colMax[j])。每格各升各的、互不牵扯。这种只顾眼前拿满、不回头的做法就是贪心，这里成立：天花板由原矩阵算出，加高超不过行列最大值，改不了别格。
先量出两条天际线，再逐格填增量
分两遍走。第一遍求 rowMax 和 colMax：扫每行、每列各取最大值。第二遍逐格算：格子 (i,j) 的天花板是 min(rowMax[i], colMax[j])，减掉现高 grid[i][j] 就是这格能加的量，所有格相加即答案。减原高别丢，加的是能往上升的那截，不是新高。
拿题面这张 4 × 4 矩阵，把 35 一格格算出来
先量两条天际线。四行最大值是 8、7、9、3，得 rowMax=[8,7,9,3]；四列最大值是 9、4、8、7，得 colMax=[9,4,8,7]。
再逐格取 min 减原高。第 0 行：min(8,9)−3=5、min(8,4)−0=4、min(8,8)−8=0、min(8,7)−4=3，小计 12。往下三行：第 1 行天花板 7、4、7、7，减原高 2、4、5、7，增量 5、0、2、0，小计 7；第 2 行天花板 9、4、8、7，减 9、2、6、3，增量 0、2、2、4，小计 8；第 3 行天花板全是 3，减 0、3、1、0，增量 3、0、2、3，小计 8。合起来 12+7+8+8=35。
天花板取 min 不取 max，这条错了满盘皆输
第一个坑是把天花板取成 max，楼会升过较小方向的最大值、顶破那个方向的天际线；取较小的才能同时压住行、列两个上界。第二个坑是忘了减 grid[i][j]，加的成了整座新高度而非增量，结果大出一截。还有人想真把楼加高再模拟看天际线，可 min(rowMax, colMax) 已保证两方向都不超，直接套公式就够。
复杂度上，求行列最大扫一遍、逐格累加再扫一遍，都是 n² 个格，时间 O(n²)；只额外存 rowMax、colMax 两条长度 n 的数组，空间 O(n)。边界都指向 0：某格同时是所在行和列的最大值时，天花板等于自身、增量为 0；矩阵全 0 时每格天花板都是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这句:每格的「天花板」是它所在行、列两个最大值里较小的那个。升到天花板既不破坏天际线,又榨干了所有可加空间。下面每一帧都在套它。
原始城市 · 4 × 4 高度矩阵：这就是 4 × 4 的高度矩阵,每个数字是一座建筑的当前高度。我们的任务:在不改变四个方向天际线的前提下,把这些建筑能加的高度全部加起来。第一步,先把每行最大、每列最大求出来。
求第 0 行的最大值：看第 0 行 3、0、8、4,里面最大的是 8(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
求第 1 行的最大值：看第 1 行 2、4、5、7,里面最大的是 7(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
求第 2 行的最大值：看第 2 行 9、2、6、3,里面最大的是 9(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
求第 3 行的最大值：看第 3 行 0、3、1、0,里面最大的是 3(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
求第 0 列的最大值：换个方向,看第 0 列 3、2、9、0,最大的是 9。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
求第 1 列的最大值：换个方向,看第 1 列 0、4、2、3,最大的是 4。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
求第 2 列的最大值：换个方向,看第 2 列 8、5、6、1,最大的是 8。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
求第 3 列的最大值：换个方向,看第 3 列 4、7、3、0,最大的是 7。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
两组天际线已就位：rowMax 是 8、7、9、3,colMax 是 9、4、8、7。接下来对每一格,取它所在行最大和列最大里较小的那个当天花板,减去原高就是这一格能加的量。我们从左上角一格一格扫,边扫边累加。
格 (0,0) · 取 min 算增量：当前格 3：本行最大 8、本列最大 9，较小的是 8（被行卡住），就是它的天花板。能加 5，累计来到 5。
格 (0,1) · 取 min 算增量：当前格 0：本行最大 8、本列最大 4，较小的是 4（被列卡住），就是它的天花板。能加 4，累计来到 9。
格 (0,2) · 取 min 算增量：当前格 8：本行最大 8、本列最大 8，较小的是 8（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 9。
格 (0,3) · 取 min 算增量：当前格 4：本行最大 8、本列最大 7，较小的是 7（被列卡住），就是它的天花板。能加 3，累计来到 12。
格 (1,0) · 取 min 算增量：当前格 2：本行最大 7、本列最大 9，较小的是 7（被行卡住），就是它的天花板。能加 5，累计来到 17。
格 (1,1) · 取 min 算增量：当前格 4：本行最大 7、本列最大 4，较小的是 4（被列卡住），就是它的天花板。原本就到顶,加不了，累计来到 17。
格 (1,2) · 取 min 算增量：当前格 5：本行最大 7、本列最大 8，较小的是 7（被行卡住），就是它的天花板。能加 2，累计来到 19。
格 (1,3) · 取 min 算增量：当前格 7：本行最大 7、本列最大 7，较小的是 7（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 19。
格 (2,0) · 取 min 算增量：当前格 9：本行最大 9、本列最大 9，较小的是 9（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 19。
格 (2,1) · 取 min 算增量：当前格 2：本行最大 9、本列最大 4，较小的是 4（被列卡住），就是它的天花板。能加 2，累计来到 21。
格 (2,2) · 取 min 算增量：当前格 6：本行最大 9、本列最大 8，较小的是 8（被列卡住），就是它的天花板。能加 2，累计来到 23。
格 (2,3) · 取 min 算增量：当前格 3：本行最大 9、本列最大 7，较小的是 7（被列卡住），就是它的天花板。能加 4，累计来到 27。
格 (3,0) · 取 min 算增量：当前格 0：本行最大 3、本列最大 9，较小的是 3（被行卡住），就是它的天花板。能加 3，累计来到 30。
格 (3,1) · 取 min 算增量：当前格 3：本行最大 3、本列最大 4，较小的是 3（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 30。
格 (3,2) · 取 min 算增量：当前格 1：本行最大 3、本列最大 8，较小的是 3（被行卡住），就是它的天花板。能加 2，累计来到 32。
格 (3,3) · 取 min 算增量：当前格 0：本行最大 3、本列最大 7，较小的是 3（被行卡住），就是它的天花板。能加 3，累计来到 35。
抬升后的城市 · 天际线不变：十六格全算完,这是抬升后的城市。你可以验一下:每行最大仍是 8、7、9、3,每列最大仍是 9、4、8、7,四个方向的天际线一点没变。所有增量加起来正好 35，就是答案。
边界都指向 0:当某格已经同时是行最大和列最大时,它就动不了。
两个高频追问:贪心为何成立(各格独立),以及空间为何是 O(n)。
参考代码
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 maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int: row_max = [max(row) for row in grid] col_max = [max(col) for col in zip(*grid)] return sum( min(row_max[i], col_max[j]) - x for i, row in enumerate(grid) for j, x in enumerate(row) )复杂度
- 时间：O(n²)，两遍遍历矩阵:一遍求行列最大,一遍逐格累加
- 空间：O(n)，只额外存 rowMax、colMax 两个长度 n 的数组
易错点
面试追问把动画讲成自己的话
追问为什么贪心地把每格独立升到自己的天花板,就能得到全局最大总增量?
追问能不能不用额外数组,空间做到 O(1)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
推多米诺
LeetCode 838 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题