• This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .

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[0].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 .

---

Answer key

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 = [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
        # 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

---