LeetCode 807. 保持城市天际线

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为
标签
数组 矩阵 贪心

题目描述

✅ 807. 保持城市天际线

image-20260928224858428

image-20260928224858429

image-20260928224858431

题意分析

网格中的每个数表示一栋楼的高度，可以给任意楼增加高度，但不能降低。要求从东、南、西、北四个方向看到的城市天际线保持原样，求所有楼能增加的高度总和的最大值。

沿一行看过去，轮廓高度只由这一行的最高楼决定；反方向看同一行也是相同的最高值，列方向同理。因此四个视角归结为保持每一行、每一列原本的最大高度。返回增加量，不是改造后的楼高总和。

解法：行列最大值

核心思路

[!blue]

先保存原网格每行的最高值 rowMax[i] 和每列的最高值 colMax[j]。位置 (i, j) 的新高度不能超过本行最大值，否则会抬高行轮廓；也不能超过本列最大值，否则会抬高列轮廓。因此它的独立上界是 min(rowMax[i], colMax[j])。

原高度本来就不超过这两个最大值，所以该上界不会低于原楼高，只需增加、不必降低。将当前楼直接升到上界，就是在不突破任何一侧约束时，这一格能取得的最大增量。

所有格子同时升到各自上界也合法。每个新高度都不超过对应行最大值，因此行的最高值不会增加；原本达到行最大值的那栋楼不被降低，所以最高值也不会减少。列方向完全相同，因此整座城市仍保留原来的两组轮廓。

每个格子的理论上界能够同时实现，不存在一栋升高后必须让另一栋少升的冲突。因此把各格的上界减去原高度再相加，就达到了全局最大增加量，无需逐次模拟建筑变化。

解题步骤

  1. 遍历网格，完整统计每一行和每一列的原始最大高度。
  2. 再次遍历每个位置，取行、列最大值的较小者作为该楼新高度上界。
  3. 将上界减去当前高度所得增量累加到答案。
  4. 返回总增量，原网格无需实际修改。

代码实现

class Solution {
    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 {
    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(mn)$，对 m 行、n 列网格执行两次扫描；题目中的方形网格是其中的特殊情况。
  • 空间复杂度：$O(m + n)$，分别保存行最大值和列最大值。

关键点总结

[!green]

  • 四向天际线只要求保持两组行列最大值。
  • 同时受到两个上界限制，单格最高只能取其中较小者。
  • 原最高楼不下降、新楼不超界，保证所有位置一起升高仍保持轮廓。
  • 求和对象是新旧高度之差，直接计算即可，不必更新输入。

易错点总结

[!yellow]

  • 使用行列最大值中的较大者，会突破较低那一侧的轮廓。
  • 只约束某一行或某一列，不能同时保证两个方向的天际线。
  • 最大值尚未统计完就计算增量，会使用不完整的约束，低估可增加高度。
  • 直接累加上界而不减原高度，会返回最终总高度而不是增加量。

相似题目

题目 难度 关联与区别
42. 接雨水 困难 同样由两侧限制取较小上界，本题上界来自当前行和列最大值，原题来自左右最高边界。
883. 三维形体投影面积 简单 同样按行列最大高度概括天际信息，原题累计投影面积，本题在保持这些最大值不变时增加格子高度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/37842631
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！