题目描述
思路解析动画文字版
记牢这句:每格的「天花板」是它所在行、列两个最大值里较小的那个。升到天花板既不破坏天际线,又榨干了所有可加空间。下面每一帧都在套它。
原始城市 · 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题