【算法学习】807. 保持城市天际线（java / c / c++ / python / go / rust）

2022-12-06 23:18:32

807. 保持城市天际线：

在二维数组grid中，gridi代表位于某处的建筑物的高度。我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。高度 0 也被认为是建筑物。

最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。请看下面的例子。

建筑物高度可以增加的最大总和是多少？

样例 1

输入：
  
  grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
  
输出：

  35
  
解释：
  
  The grid is:
  [ [3, 0, 8, 4], 
    [2, 4, 5, 7],
    [9, 2, 6, 3],
    [0, 3, 1, 0] ]
    
  从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
  从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]
    
  在不影响天际线的情况下对建筑物进行增高后，新数组如下：
    
  gridNew = [ [8, 4, 8, 7],
              [7, 4, 7, 7],
              [9, 4, 8, 7],
              [3, 3, 3, 3] ]

提示

1 < grid.length = grid[0].length <= 50。
gridi 的高度范围是： [0, 100]。
一座建筑物占据一个gridi：换言之，它们是 1 x 1 x gridi 的长方体。

分析

首先要明白天际线是什么：城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。影响轮廓的就是你所看方向上，每一行或列上最高的建筑的高度。
所以我们把所看方向上较低的建筑增高到恰好是最高建筑一样的高度，就是在不影响天际线的情况下，建筑物能增加的最大高度。
但是四个方向的天际线都不能影响，思考一下就知道上和下，左和右的天际线是一致的。那么我们只需要在增加建筑物高度的时候，同时考虑2个天际线就可以了，并且我们只能增加到其中较低的高度才能都不影响。
可以分两步，第一步先算出天际线，第二步统计结果。

题解

java

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int   n        = grid.length;

        // 算出天际线
        int[] rowMaxes = new int[n];
        int[] colMaxes = new int[n];
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
                colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
            }
        }

        int ans = 0;

        // 计算结果
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c];
            }
        }

        return ans;
    }
}

c

int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){
    // 算出天际线
    int rowMaxes[gridSize];
    int colMaxes[*gridColSize];
    memset(rowMaxes, 0, sizeof(rowMaxes));
    memset(colMaxes, 0, sizeof(colMaxes));
    for (int r = 0; r < gridSize; ++r) {
        for (int c = 0; c < *gridColSize; ++c) {
            rowMaxes[r] = fmax(rowMaxes[r], grid[r][c]);
            colMaxes[c] = fmax(colMaxes[c], grid[r][c]);
        }
    }

    int ans = 0;

    // 计算结果
    for (int r = 0; r < gridSize; ++r) {
        for (int c = 0; c < *gridColSize; ++c) {
            ans += fmin(rowMaxes[r], colMaxes[c]) - grid[r][c];
        }
    }

    return ans;
}

c++

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int   n        = grid.size();

        // 算出天际线
        vector<int> rowMaxes(n, 0);
        vector<int> colMaxes(n, 0);
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                rowMaxes[r] = max(rowMaxes[r], grid[r][c]);
                colMaxes[c] = max(colMaxes[c], grid[r][c]);
            }
        }

        int ans = 0;

        // 计算结果
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c];
            }
        }

        return ans;
    }
};

python

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # 算出天际线
        rowMaxes = [0] * n
        colMaxes = [0] * n
        for r in range(n):
            for c in range(n):
                rowMaxes[r] = max(rowMaxes[r], grid[r][c])
                colMaxes[c] = max(colMaxes[c], grid[r][c])
        ans = 0
        #计算结果
        for r in range(n):
            for c in range(n):
                ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
        return ans

go

func maxIncreaseKeepingSkyline(grid [][]int) int {
    n := len(grid)

    // 算出天际线
    rowMaxes := make([]int, n)
    colMaxes := make([]int, n)
    for r := 0; r < n; r++ {
        for c := 0; c < n; c++ {
            rowMaxes[r] = max(rowMaxes[r], grid[r][c])
            colMaxes[c] = max(colMaxes[c], grid[r][c])
        }
    }

    ans := 0

    // 计算结果
    for r := 0; r < n; r++ {
        for c := 0; c < n; c++ {
            ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
        }
    }

    return ans
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

rust

impl Solution {
    pub fn max_increase_keeping_skyline(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();

        // 算出天际线
        let mut rowMaxes = vec![0; n];
        let mut colMaxes = vec![0; n];
        for r in 0..n {
            for c in 0..n {
                rowMaxes[r] = rowMaxes[r].max(grid[r][c]);
                colMaxes[c] = colMaxes[c].max(grid[r][c]);
            }
        }

        let mut ans = 0;

        // 计算结果
        for r in 0..n {
            for c in 0..n {
                ans += rowMaxes[r].min(colMaxes[c]) - grid[r][c];
            }
        }

        return ans;
    }
}

原题传送门：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

码农公寓