# [algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)

2022-01-30 13:40:02

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~

# 807. Keep the city skyline ：

In a two-dimensional array grid in ,grid[i][j] Represents the height of a building located somewhere . We are allowed to increase any amount （ The number of different buildings may be different ） The height of the building . Height 0 It's also considered a building .

Last , From all four directions of the new array （ That's the top , Bottom , Left and right ） Watched “ The skyline ” Must be the same as the skyline of the original array . The skyline of the city is when viewed from a distance , The outer contour of a rectangle formed by all buildings . Please see the following example .

What is the maximum sum of the height of the building that can be increased ？

# Examples 1

`````` Input ：
grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output ：
35
explain ：
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]

From the vertical direction of the array （ That's the top , Bottom ） see “ The skyline ” yes ：[9, 4, 8, 7]
From the horizontal （ On the left , On the right side ） see “ The skyline ” yes ：[8, 7, 9, 3]

After heightening the building without affecting the skyline , The new array is as follows ：

gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
Copy code ``````

# Tips

• 1 < grid.length = grid.length <= 50.
• grid[i][j] The height range of is ： [0, 100].
• A building occupies one grid[i][j]： In other words , They are 1 x 1 x grid[i][j] The cuboid of .

# analysis

• First, understand what the skyline is ： The skyline of the city is when viewed from a distance , The outer contour of a rectangle formed by all buildings . What affects the outline is the direction you look , The height of the tallest building in each row or column .
• So we raise the lower building in the direction we see to exactly the same height as the highest building , Without affecting the skyline , The maximum height that a building can increase .
• But the skyline in four directions can't affect , Think about it and you'll know up and down , The left and right skylines are consistent . Then we just need to increase the height of the building , Consider at the same time 2 Just a skyline , And we can only increase to a lower height without affecting .
• There are two steps , The first step is to calculate the skyline , The second step is to count the results .

## java

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

//  Figure out the skyline
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;

//  The result of the calculation is
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;
}
}
Copy code ``````

## c

``````int maxIncreaseKeepingSkyline(int** grid, int gridSize, int* gridColSize){
//  Figure out the skyline
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;

//  The result of the calculation is
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;
}
Copy code ``````

## c++

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

//  Figure out the skyline
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;

//  The result of the calculation is
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;
}
};
Copy code ``````

## python

``````class Solution:
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
n = len(grid)
#  Figure out the skyline
rowMaxes =  * n
colMaxes =  * 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
# The result of the calculation is
for r in range(n):
for c in range(n):
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
return ans
Copy code ``````

## go

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

//  Figure out the skyline
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

//  The result of the calculation is
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
}
Copy code ``````

## rust

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

//  Figure out the skyline
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;

//  The result of the calculation is
for r in 0..n {
for c in 0..n {
ans += rowMaxes[r].min(colMaxes[c]) - grid[r][c];
}
}

return ans;
}
}
Copy code `````` # Original title transmission gate ：https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/

Welcome to discuss in the comment area , Nuggets officials will be in Digging force Star Program After the event , Draw... In the comment area 100 Around the Nuggets , For details of the lucky draw, see the activity article