- This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog
807. Maintenance of urban skylines:
In the two-dimensional array grid, the grid[I][j] represents the height of a building located somewhere. We are allowed to increase the height of any number of buildings (the number of different buildings may vary). Height 0 is also considered a building.
Finally, the skyline viewed from all four directions of the new array (top, bottom, left, and right) must be the same as the skyline of the original array. The city skyline is a rectangular exterior outline formed by all the buildings when viewed from a distance. Take a look at the following example.
What is the maximum sum that can be increased in building height?
Sample 1
Input: The grid = [,0,8,4 [3], [2,4,5,7],,2,6,3 [9], [0,3,1,0]] output: 35 explanation: The grid is: [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]] Looking at the skyline from the vertical direction (top, bottom) is: GridNew = [[8, 4, 8, 7], [7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3]]Copy the codeprompt
- 1 < grid.length = grid[0]. Length <= 50
- Grid [I][J] height range is: [0, 100].
- A building occupies a grid[I][j] : in other words, they are cuboids of 1 x 1 x grid[I][j].
Analysis of the
- Start by understanding what a skyline is: a city’s skyline is a rectangular exterior outline formed by all the buildings when viewed from afar. What affects the contour is the height of the tallest building in each row or column in the direction you are looking at.
- So we raised the lower building in the direction we were looking at to exactly the same height as the tallest building, which is the maximum height a building can add without affecting the skyline.
- But the skylines in the four directions are not affected. If you think about it, you know that the skylines up and down, left and right are the same. So we only need to consider both skylines when increasing the building height, and we can only increase the lower height of the two skylines without affecting both.
- It can be divided into two steps. The first step is to calculate the skyline, and 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;
// Calculate the result
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) { ans += Math.min(rowMaxes[r], colMaxes[c]) - grid[r][c]; }}returnans; }}Copy the codec
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;
// Calculate the result
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 the codec++
class Solution {
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int n = grid.size(a);// 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;
// Calculate the result
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c) {
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]; }}returnans; }};Copy the codepython
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
# Calculation results
for r in range(n):
for c in range(n):
ans += min(rowMaxes[r], colMaxes[c]) - grid[r][c]
return ans
Copy the codego
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
// Calculate the result
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 the coderust
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;
// Calculate the result
for r in 0..n {
for c in 0. n { ans += rowMaxes[r].min(colMaxes[c]) - grid[r][c]; }}returnans; }}Copy the code
Portal: https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline/
Please feel free to discuss in the comments section. The nuggets will draw 100 nuggets in the comments section after the diggnation project. See the event article for details