LeetCode 807. 保持城市天际线
目录
题目描述
题意分析
grid[i][j]是坐落在第i行第j列的一栋楼的高度。允许把任意多栋楼加高任意高度（只能加不能减），但要求加高之后，从东、南、西、北四个方向看到的天际线轮廓与原来完全一致。问所有楼房增加的高度之和最大是多少。先把「天际线」翻译成数组语言。从北或南看过去，第
j列的所有楼重叠在一起，看到的轮廓高度就是这一列的最大值colMax[j]；从东或西看过去，第i行的所有楼重叠，轮廓高度是这一行的最大值rowMax[i]。四个方向看似是四组约束，其实只有两组：每一行的最大值不能变、每一列的最大值不能变。北和南给出的是同一个colMax，东和西给出的是同一个rowMax。再注意「只能加高」这个方向性：单调加高只可能让某行某列的最大值变大，绝不可能变小。所以「最大值不变」等价于「最大值不变大」，也就是每个格子的新高度都不许超过它所在行的原最大值，也不许超过它所在列的原最大值。约束从「等式」松弛成了「不等式」，这是本题能一步到位的根本原因。
约束里
grid是n × n方阵、n不超过 50、高度在 0 到 100 之间。规模小到怎么写都不会超时，说明考点不是优化而是能不能把约束拆干净。高度非负这一点也很有用，它让最大值数组可以安全地从 0 开始初始化。边界：格子本身可能就是行或列的最大值，此时它一点都不能加高，增量为 0；高度可以是 0，
grid中全 0 时答案就是 0。
解法：行列最大值
核心思路
暴力思路是把「加高多少」当成待求变量，对每个格子二分它能加到多高，每试一次就重新扫一遍整个矩阵验证天际线有没有变。这样的代价是 $O(m \cdot n \cdot \log H \cdot m \cdot n)$，而且更麻烦的是——加高格子 A 之后再判断格子 B，两者会不会互相影响？只要不确认这一点，贪心就没有依据。
瓶颈其实不是速度，而是这层「是否互相影响」的顾虑。把它拆开看：格子
(i, j)的高度只出现在两个统计量里——第i行的最大值和第j列的最大值。它对第i'行（i' ≠ i）、第j'列（j' ≠ j）的轮廓毫无贡献。于是每个格子的约束是完全独立的：只要grid[i][j]的新值同时满足≤ rowMax[i]且≤ colMax[j]，它就不会破坏任何一条轮廓，而且这个判断跟别的格子怎么改毫无关系。由此得到每个格子的高度上界：$\min(rowMax[i],\ colMax[j])$。既然要总增量最大，又互不干扰，就让每个格子都顶到自己的上界，增量 $\min(rowMax[i], colMax[j]) - grid[i][j]$ 逐格累加。这个值一定非负，因为
grid[i][j]本身既参与了rowMax[i]的取最大也参与了colMax[j]的取最大，必然同时不超过两者。但还差一步论证：所有格子同时顶到上界之后，
rowMax和colMax真的没变吗？上界只保证了「不会变大」，还要说明「不会变小」——也就是原来的最大值仍然被某个格子取到。取第i行的最大值所在的格子(i, j^*)，有grid[i][j^*] = rowMax[i]。因为它也是第j^*列的一个元素，所以colMax[j^*] ≥ grid[i][j^*] = rowMax[i]，于是它的上界 $\min(rowMax[i], colMax[j^*]) = rowMax[i]$，也就是这个格子根本没被加高，第i行的最大值仍然原封不动是rowMax[i]。列的论证完全对称。至此不变量成立：把每个格子独立抬到 $\min(rowMax[i], colMax[j])$ 后，所有
rowMax与colMax都保持原值，因而四个方向的天际线不变。既然每个格子都取到了它各自的上界，总和自然是可能的最大值——这是「逐项上界可同时达到，故上界之和即为最优」的典型结构，贪心在这里不需要交换论证，因为根本不存在取舍。
解题步骤
- 第一趟：求
rowMax与colMax。一次双重循环里同时更新两个数组——遍历到grid[i][j]时既拿它更新rowMax[i]也更新colMax[j]。两个数组都初始化为全 0，这依赖题目保证高度非负；若允许负数就必须初始化为极小值或首元素。- 两趟必须分开。不能一边算最大值一边累加答案：处理第 0 行时下面的行还没扫到，
colMax是残缺的，算出来的上界会偏小。只有第一趟完整结束，rowMax和colMax才是全局真值。- 第二趟：逐格累加增量。对每个
(i, j)取min(rowMax[i], colMax[j]) - grid[i][j]累加。这里的下标搭配必须是rowMax[i]配colMax[j]，一个用行号一个用列号，写成同一个下标是最常见的手滑。- 取
min而不是max。两条约束是「同时满足」的合取关系，能容纳的最大值是两个上界中较小的那个。- 累加的是增量而不是新高度。题目问的是「增加的高度之和」。
- 不需要真的修改
grid，也不需要第三趟验证——正确性已由上面的论证保证。以官方样例
grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]走一遍。第一趟得到
rowMax = [8, 7, 9, 3]（各行最大值 8、7、9、3），colMax = [9, 4, 8, 7]（各列最大值 9、4、8、7）。
第二趟第 0 行（rowMax[0] = 8）：(0,0)上界min(8,9) = 8，增量8-3 = 5；(0,1)上界min(8,4) = 4，增量4-0 = 4；(0,2)上界min(8,8) = 8，增量8-8 = 0（它正是本行最大值，一点不能动）；(0,3)上界min(8,7) = 7，增量7-4 = 3。本行小计 12。
第 1 行（rowMax[1] = 7）：上界依次为 7、4、7、7，增量7-2 = 5、4-4 = 0、7-5 = 2、7-7 = 0。本行小计 7。
第 2 行（rowMax[2] = 9）：上界依次为 9、4、8、7，增量9-9 = 0、4-2 = 2、8-6 = 2、7-3 = 4。本行小计 8。
第 3 行（rowMax[3] = 3）：上界依次为 3、3、3、3（这一行的最大值只有 3，全被它压住），增量3-0 = 3、3-3 = 0、3-1 = 2、3-0 = 3。本行小计 8。
总计12 + 7 + 8 + 8 = 35，与期望答案一致。反过来验证天际线：改造后每行的最大值依次是 8、7、9、3，每列的最大值依次是 9、4、8、7，与原来完全相同——因为每行、每列原本的最高那栋楼（如
(0,2)的 8、(2,0)的 9）增量恰好为 0，轮廓被它们钉死了。
代码实现
class Solution {
// 对每个格子，其可增加的高度为 min(rowMax[i], colMax[j]) - grid[i][j]。
public int maxIncreaseKeepingSkyline(int[][] grid) {
int m = grid.length;
int 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 answer = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
answer += Math.min(rowMax[i], colMax[j]) - grid[i][j];
}
}
return answer;
}
}
func maxIncreaseKeepingSkyline(grid [][]int) int {
// 对每个格子，其可增加的高度为 min(rowMax[i], colMax[j]) - grid[i][j]。
m := len(grid)
n := len(grid[0])
rowMax := make([]int, m)
colMax := make([]int, n)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] > rowMax[i] {
rowMax[i] = grid[i][j]
}
if grid[i][j] > colMax[j] {
colMax[j] = grid[i][j]
}
}
}
answer := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
limit := rowMax[i]
if colMax[j] < limit {
limit = colMax[j]
}
answer += limit - grid[i][j]
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(m \cdot n)$，其中 $m$、$n$ 为矩阵行列数。两趟完整的双重循环，每格各做常数次比较与加减，没有任何回退或重算——凭的是「每个格子的上界只由
rowMax[i]与colMax[j]决定，与其他格子的取值无关」，因此一次算出即为终值。- 空间复杂度：$O(m + n)$，两个长度分别为 $m$ 和 $n$ 的最大值数组。凭的是把二维矩阵的约束压成了两组一维统计量；如果允许原地改写
grid并接受两趟以上的扫描，这部分也无法再省——行列最大值必须先全部就位才能开始累加。
关键点总结
- 先把题面的自然语言翻译成数组语言：「四个方向的天际线」= 行最大值数组 + 列最大值数组，东西同源、南北同源，四组约束实为两组。审题阶段的化简往往比后面的编码更值钱。
- 「只能增加」把「保持不变」松弛成「不超过」，等式约束变不等式约束，问题从构造变成了求上界。看到单调方向的操作限制就要往这上面想。
- 每个格子只影响它所在的一行一列，格子之间互不干扰，所以「逐项取上界」直接就是全局最优，不需要交换论证或反证。这类「约束可分解」的结构是贪心最干净的一种。
- 贪心题一定要补上「上界能同时取到」的论证：行最大值所在的格子因为 $\min$ 的另一半必然更大而增量为 0，天际线被它自己钉住。面试时这段话是拿分点。
- 必须两趟：统计量要先全局就位，再基于它做决策。一趟边算边用是这类题最普遍的错误。
- 面试视角：这道题代码只有十几行，面试官真正在听的是三句话——天际线等价于行列最大值、只增不减所以约束是上界、每格独立所以逐格顶到 $\min$ 即最优。主动把这三句说完再写代码，比默默写完等提问要好；如果被追问「怎么证明这是最大值」，就把那个「行最大值格子增量为 0」的论证讲出来。
易错点总结
- 一趟边算最大值边累加：
grid = [[1,2],[3,4]]处理(0,0)时第 1 行还没扫到，colMax[0]只有 1，上界算成min(2,1) = 1，增量 0；正确的上界是min(2,3) = 2，增量 1。最终答案少算，且随输入行序变化而变化。min写成max：grid = [[1,2],[3,4]]中(0,0)会被抬到max(2,3) = 3，第 0 行的最大值从 2 变成 3，从东西方向看的轮廓被抬高，方案非法。- 下标写成
min(rowMax[i], colMax[i])：在官方样例里(0,1)会用colMax[0] = 9而不是colMax[1] = 4，上界从 4 变成 8，这个格子被抬到 8，第 1 列最大值从 4 暴涨到 8，答案也从 35 变大。方阵输入不会越界，所以这个错误跑起来「有结果」，最难被发现。- 累加新高度而不是增量：
grid = [[1,2],[3,4]]会返回2+2+3+4 = 11，而正确答案是1+0+0+0 = 1。- 只维护
rowMax、忘了colMax：grid = [[1,2],[3,4]]中(0,0)抬到 2、(1,0)抬到 4，第 0 列最大值从 3 变成 4，南北方向的轮廓改变；答案算成 2，比正确的 1 多。colMax数组开成new int[m]：本题是n × n方阵所以侥幸不越界，一旦换成m ≠ n的矩阵变体（比如 3 行 5 列）就会在colMax[3]处直接数组越界。- 把
rowMax/colMax初始化成Integer.MAX_VALUE或首行首列的值再取max：前者让所有上界都变成另一个数组的值，grid = [[1,2],[3,4]]会把(0,0)抬到 3；后者在写成rowMax[i] = grid[0][i]这种行列混淆的形式时同样出错。高度非负，全 0 初始化才是与题目约束匹配的写法。- 在第二趟里就地改写
grid[i][j] = limit之后又重算一次最大值：改写后的矩阵行列最大值虽然不变，但如果再走一遍累加逻辑，增量会被算成 0 并覆盖原答案，出现「第二次调用返回 0」的诡异行为。本题根本不需要改写grid。- 误以为东、西是两组不同约束而分别记录行首、行尾的可见高度：
[[1,3,2]]从左看和从右看都是 3，行内其余楼被最高的那栋完全遮挡，两个方向给出的是同一个值。多建两个数组只会引入不一致。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 861. 翻转矩阵后的得分 | 中等 | 同样按行列拆解贪心，但操作是整行整列取反且有先后顺序，各列不再互相独立 |
| 73. 矩阵置零 | 中等 | 也靠两组行列标记，难点在于要求 $O(1)$ 空间，得把标记压进矩阵首行首列 |
| 867. 转置矩阵 | 简单 | 只做行列下标互换，不涉及任何统计量，是行列思维的最简形态 |
| 48. 旋转图像 | 中等 | 要求原地变换，考的是四点循环交换或「转置 + 翻转」的分解，而非聚合统计 |
| 566. 重塑矩阵 | 简单 | 考一维下标与二维坐标的互相换算，配合可行性判断 |
| 498. 对角线遍历 | 中等 | 聚合方向从行列换成对角线（i + j 为常数），边界转向规则是主要难点 |
| 54. 螺旋矩阵 | 中等 | 用四条边界变量控制访问顺序，考的是循环收缩而非统计量复用 |