current position：Home>[algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)
[algorithm learning] 807 Maintain the city skyline (Java / C / C + + / Python / go / trust)
20220130 13:40:02 【White hat of the second leader】
 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 thumbsup 】【 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 twodimensional 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://leetcodecn.com/problems/maxincreasetokeepcityskyline/
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
copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201301340005817.html
The sidebar is recommended
 Python code reading (Part 44): find the location of qualified elements
 Elegant implementation of Django model field encryption
 40 Python entry applet
 Pandas comprehensive application
 Chapter 2: Fundamentals of python3 character string
 Python pyplot draws a parallel histogram, and the xaxis value is displayed in the center of the two histograms
 [Python crawler] detailed explanation of selenium from introduction to actual combat [1]
 Curl to Python self use version
 Python visualization  3D drawing solutions pyecharts, Matplotlib, openpyxl
 Use python, opencv's meanshift and CAMSHIFT algorithms to find and track objects in video
guess what you like

Using python, opencv obtains and changes pixels, modifies image channels, and trims ROI

[Python data collection] university ranking data collection

[Python data collection] stock information collection

Python game development, pyGame module, python takes you to realize a magic tower game from scratch (2)

Python solves the problem of suspending execution after clicking the mouse in CMD window (fast editing mode is prohibited)

[Python from introduction to mastery] (II) how to run Python? What are the good development tools (pycharm)

Python type hints from introduction to practice

Python notes (IX): basic operation of dictionary

Python notes (8): basic operations of collections

Python notes (VII): definition and use of tuples
Random recommended
 Python notes (6): definition and use of lists
 Python notes (V): string operation
 Python notes (IV): use of functions and modules
 Python notes (3): conditional statements and circular statements
 Python notes (II): lexical structure
 Notes on python (I): getting to know Python
 [Python data structure series]  tree and binary tree  basic knowledge  knowledge point explanation + code implementation
 [Python daily homework] Day7: how to combine two dictionaries in an expression?
 How to implement a custom list or dictionary in Python
 15 advanced Python tips for experienced programmers
 Python string method tutorial  how to use the find() and replace() functions on Python strings
 Python computer network basics
 Python crawler series: crawling global airport information
 Python crawler series: crawling global port information
 How to calculate unique values using pandas groupby
 Application of builtin distribution of Monte Carlo simulation SciPy with Python
 Gradient lifting method and its implementation in Python
 Pandas: how to group and calculate by index
 Can you create an empty pandas data frame and fill it in?
 Python basic exercises teaching! can't? (practice makes perfect)
 Exploratory data analysis (EDA) in Python using SQL and Seaborn (SNS).
 Turn audio into shareable video with Python and ffmpeg
 Using rbind in python (equivalent to R)
 Pandas: how to create an empty data frame with column names
 Talk about quantifying investment using Python
 Python, image restoration in opencv  CV2 inpaint
 Python notes (14): advanced technologies such as objectoriented programming
 Python notes (13): operations such as objectoriented programming
 Python notes (12): inheritance such as objectoriented programming
 Chapter 2: Fundamentals of python5 Boolean
 Python notes (11): encapsulation such as objectoriented programming
 Python notes (10): concepts such as objectoriented programming
 Gradient lifting method and its implementation in Python
 Van * Python  simple crawling of a site course
 Chapter 1 preliminary knowledge of pandas (list derivation and conditional assignment, anonymous function and map method, zip object and enumerate method, NP basis)
 Nanny tutorial! Build VIM into an IDE (Python)
 Fourier transform of Python OpenCV image processing, lesson 52
 Introduction to python (III) network request and analysis
 China Merchants Bank credit card number recognition project (Part I), python OpenCV image processing journey, Part 53
 Python practice  capture 58 rental information and store it in MySQL database