LeetCode 807中等贪心 · 排序
保持城市天际线 图解题解
这道题到底在问什么
给定 n × n 整数矩阵 grid,grid[r][c] 是该建筑高度。可给任意建筑加任意高度,但从东、南、西、北看到的天际线都不能变。返回所有建筑能增加的最大高度增量之和。
- 输入
- grid=[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
- 输出
- 35
- 输入
- grid=[[0,0,0],[0,0,0],[0,0,0]]
- 输出
- 0 （全 0,谁也加不了）
最优解：一步一步想明白
- 3记牢这句:每格的「天花板」是它所在行、列两个最大值里较小的那个。升到天花板既不破坏天际线,又榨干了所有可加空间。下面每一帧都在套它。
- 4每格数字 = 建筑高度这就是 4 × 4 的高度矩阵,每个数字是一座建筑的当前高度。我们的任务:在不改变四个方向天际线的前提下,把这些建筑能加的高度全部加起来。第一步,先把每行最大、每列最大求出来。
- 5橙色 = 本行;高亮 = 本行最大看第 0 行 3、0、8、4,里面最大的是 8(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
- 6橙色 = 本行;高亮 = 本行最大看第 1 行 2、4、5、7,里面最大的是 7(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
- 7橙色 = 本行;高亮 = 本行最大看第 2 行 9、2、6、3,里面最大的是 9(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
- 8橙色 = 本行;高亮 = 本行最大看第 3 行 0、3、1、0,里面最大的是 3(高亮那格)。这就是从东西方向看这一行时,天际线的高度。记进 rowMax,继续下一行。
- 9橙色 = 本列;高亮 = 本列最大换个方向,看第 0 列 3、2、9、0,最大的是 9。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
- 10橙色 = 本列;高亮 = 本列最大换个方向,看第 1 列 0、4、2、3,最大的是 4。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
- 11橙色 = 本列;高亮 = 本列最大换个方向,看第 2 列 8、5、6、1,最大的是 8。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
- 12橙色 = 本列;高亮 = 本列最大换个方向,看第 3 列 4、7、3、0,最大的是 7。这是从南北方向看这一列的天际线高度。记进 colMax,四列扫完就两组数据齐了。
- 13rowMax 与 colMax 都已算好rowMax 是 8、7、9、3,colMax 是 9、4、8、7。接下来对每一格,取它所在行最大和列最大里较小的那个当天花板,减去原高就是这一格能加的量。我们从左上角一格一格扫,边扫边累加。
- 14紫色 = 当前格;橙色 = 行/列最大来源当前格 3：本行最大 8、本列最大 9，较小的是 8（被行卡住），就是它的天花板。能加 5，累计来到 5。
- 15紫色 = 当前格;橙色 = 行/列最大来源当前格 0：本行最大 8、本列最大 4，较小的是 4（被列卡住），就是它的天花板。能加 4，累计来到 9。
- 16紫色 = 当前格;橙色 = 行/列最大来源当前格 8：本行最大 8、本列最大 8，较小的是 8（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 9。
- 17紫色 = 当前格;橙色 = 行/列最大来源当前格 4：本行最大 8、本列最大 7，较小的是 7（被列卡住），就是它的天花板。能加 3，累计来到 12。
- 18紫色 = 当前格;橙色 = 行/列最大来源当前格 2：本行最大 7、本列最大 9，较小的是 7（被行卡住），就是它的天花板。能加 5，累计来到 17。
- 19紫色 = 当前格;橙色 = 行/列最大来源当前格 4：本行最大 7、本列最大 4，较小的是 4（被列卡住），就是它的天花板。原本就到顶,加不了，累计来到 17。
- 20紫色 = 当前格;橙色 = 行/列最大来源当前格 5：本行最大 7、本列最大 8，较小的是 7（被行卡住），就是它的天花板。能加 2，累计来到 19。
- 21紫色 = 当前格;橙色 = 行/列最大来源当前格 7：本行最大 7、本列最大 7，较小的是 7（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 19。
- 22紫色 = 当前格;橙色 = 行/列最大来源当前格 9：本行最大 9、本列最大 9，较小的是 9（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 19。
- 23紫色 = 当前格;橙色 = 行/列最大来源当前格 2：本行最大 9、本列最大 4，较小的是 4（被列卡住），就是它的天花板。能加 2，累计来到 21。
- 24紫色 = 当前格;橙色 = 行/列最大来源当前格 6：本行最大 9、本列最大 8，较小的是 8（被列卡住），就是它的天花板。能加 2，累计来到 23。
- 25紫色 = 当前格;橙色 = 行/列最大来源当前格 3：本行最大 9、本列最大 7，较小的是 7（被列卡住），就是它的天花板。能加 4，累计来到 27。
- 26紫色 = 当前格;橙色 = 行/列最大来源当前格 0：本行最大 3、本列最大 9，较小的是 3（被行卡住），就是它的天花板。能加 3，累计来到 30。
- 27紫色 = 当前格;橙色 = 行/列最大来源当前格 3：本行最大 3、本列最大 4，较小的是 3（被行卡住），就是它的天花板。原本就到顶,加不了，累计来到 30。
- 28紫色 = 当前格;橙色 = 行/列最大来源当前格 1：本行最大 3、本列最大 8，较小的是 3（被行卡住），就是它的天花板。能加 2，累计来到 32。
- 29紫色 = 当前格;橙色 = 行/列最大来源当前格 0：本行最大 3、本列最大 7，较小的是 3（被行卡住），就是它的天花板。能加 3，累计来到 35。
- 30每格已升到自己的天花板十六格全算完,这是抬升后的城市。你可以验一下:每行最大仍是 8、7、9、3,每列最大仍是 9、4、8、7,四个方向的天际线一点没变。所有增量加起来正好 35，就是答案。
⚠️ 容易写错的地方
✗ 错：把天花板取成 max(rowMax, colMax)
✓ 对：必须取 min
升到较大那个会顶破较小方向的天际线,违反约束
✗ 错：忘了减去原高 grid[i][j]
✓ 对：增量 = 天花板 − 原高
加的是「能升的部分」,不是新高度本身
✗ 错：以为要真的去模拟加高再比天际线
✓ 对：直接用 min 公式即可
min(rowMax,colMax) 已保证两方向都不超,无需模拟
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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)
)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> rowMax(m);
vector<int> colMax(n);
for (int i = 0; i < m; ++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 < m; ++i) {
for (int j = 0; j < n; ++j) {
ans += min(rowMax[i], colMax[j]) - grid[i][j];
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[] rowMax = new int[m];
int[] colMax = new int[n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
rowMax[i] = Math.max(rowMax[i], grid[i][j]);
colMax[j] = Math.max(colMax[j], grid[i][j]);
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
}
}
return ans;
}
}复杂度
时间
O(n²)
两遍遍历矩阵:一遍求行列最大,一遍逐格累加
空间
O(n)
只额外存 rowMax、colMax 两个长度 n 的数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 保持城市天际线 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么贪心地把每格独立升到自己的天花板,就能得到全局最大总增量?+
因为各格之间互不牵制:格 (i,j) 的天花板只由 rowMax[i]、colMax[j] 决定,而 rowMax、colMax 是用原矩阵算的、不随加高变化(加高永远不超过它们,不会改变最大值)。所以每格取各自能取的最大,合起来就是全局最大,不存在「这格多加会逼另一格少加」的冲突。
能不能不用额外数组,空间做到 O(1)?+
行列最大值是必须先知道的全局信息。本动画为了讲清楚存了 rowMax、colMax 两条数组;实际可以只预存一个方向(如 colMax),逐行现算另一方向(当前行)的最大值并累加,但这一个方向仍要保留 n 个值,所以量级还是 O(n) 额外空间,降不到 O(1)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 保持城市天际线 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。