Medium

题目描述

在一个由 n x n 个街区组成的城市中，每个街区都包含一个形状像垂直正方形棱柱的建筑物。给你一个下标从 0 开始的 n x n 整数矩阵 grid，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的高度。

城市的天际线是从远处观看城市一侧时，由所有建筑物形成的外部轮廓。从每个主要方向（北、东、南和西）观看的天际线可能不同。

我们被允许增加任意数量建筑物的高度任意数量（每栋建筑物的增加量可以不同）。高度为 0 的建筑物的高度也可以增加。但是，增加建筑物的高度不应该影响从任何主要方向观察到的城市天际线。

返回在不改变从任何主要方向观察到的城市天际线的前提下，建筑物可以增加的高度的最大总和。

示例 1：

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物高度如上图中心所示。
从每个主要方向观看的天际线用红色绘制。
在不影响天际线的情况下增加建筑物高度后的网格是：
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

示例 2：

输入：grid = [[0,0,0],[0,0,0],[0,0,0]]
输出：0
解释：增加任何建筑物的高度都会导致天际线发生变化。

提示：

  • n == grid.length
  • n == grid[r].length
  • 2 <= n <= 50
  • 0 <= grid[r][c] <= 100

解题思路

解题思路

这道题的关键在于理解天际线的概念。从四个方向观察城市：

  • 从南北方向看：每列的天际线由该列的最高建筑决定
  • 从东西方向看：每行的天际线由该行的最高建筑决定

要保持天际线不变，每个位置的建筑高度不能超过：

  1. 该行的最大值
  2. 该列的最大值

因此，每个位置 (i,j) 的建筑最大可能高度为 min(该行最大值, 该列最大值)。

算法步骤：

  1. 预处理计算每行和每列的最大值
  2. 遍历每个位置，计算该位置可以达到的最大高度
  3. 累加每个位置的增加量（最大高度 - 当前高度）

这是一个贪心策略：为了最大化总增长量，每个建筑都应该增加到其约束条件下的最大可能高度。

时间复杂度为 O(n²)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> rowMax(n, 0), colMax(n, 0);
        
        // 计算每行和每列的最大值
        for (int i = 0; i < n; 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 totalIncrease = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int maxHeight = min(rowMax[i], colMax[j]);
                totalIncrease += maxHeight - grid[i][j];
            }
        }
        
        return totalIncrease;
    }
};

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)
        row_max = [max(row) for row in grid]
        col_max = [max(grid[i][j] for i in range(n)) for j in range(n)]
        
        total_increase = 0
        for i in range(n):
            for j in range(n):
                max_height = min(row_max[i], col_max[j])
                total_increase += max_height - grid[i][j]
        
        return total_increase

public class Solution {
    public int MaxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.Length;
        int[] rowMax = new int[n];
        int[] colMax = new int[n];
        
        // 计算每行和每列的最大值
        for (int i = 0; i < n; 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 totalIncrease = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int maxHeight = Math.Min(rowMax[i], colMax[j]);
                totalIncrease += maxHeight - grid[i][j];
            }
        }
        
        return totalIncrease;
    }
}

var maxIncreaseKeepingSkyline = function(grid) {
    const n = grid.length;
    const rowMax = new Array(n).fill(0);
    const colMax = new Array(n).fill(0);
    
    // 计算每行和每列的最大值
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            rowMax[i] = Math.max(rowMax[i], grid[i][j]);
            colMax[j] = Math.max(colMax[j], grid[i][j]);
        }
    }
    
    let totalIncrease = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const maxHeight = Math.min(rowMax[i], colMax[j]);
            totalIncrease += maxHeight - grid[i][j];
        }
    }
    
    return totalIncrease;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²) - 需要遍历矩阵两次，第一次计算行列最大值，第二次计算总增长量
空间复杂度O(n) - 需要额外的数组存储每行和每列的最大值