【算法学习】807 保持城市天际线（java / c /

发表于
  • 本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

非常感谢你阅读本文~
欢迎【👍点赞】【⭐收藏】【📝评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://juejin.cn/user/2771185768884824/posts 博客原创~

  1. 保持城市天际线：

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

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

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

样例 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
less复制代码输入：
	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。
  • grid[i][j] 的高度范围是： [0, 100]。
  • 一座建筑物占据一个grid[i][j]：换言之，它们是 1 x 1 x grid[i][j] 的长方体。

分析

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

题解

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
cpp复制代码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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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/

欢迎在评论区讨论，掘金官方将在掘力星计划活动结束后，在评论区抽送100份掘金周边，抽奖详情见活动文章

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%