保持城市天际线 图解题解

十六座楼能加多高，还不改四个方向的天际线

给一个 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。

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;
    }
}