#807

Max Increase to Keep City Skyline

pupil · 405 · lc medium +24 · verified · 86.4% accepted · 2,665 likes · top 97%

Description

A city consists of an n x n block grid, where each block holds one building shaped as a vertical prism. You are given a 0-indexed n x n matrix grid where grid[r][c] is the height of the building at row r, column c.

When the city is viewed from a distance in any direction (north, east, south, or west), it has a skyline — the outer silhouette formed by the tallest buildings in each line of sight.

You may increase the height of any building by any amount (including buildings with height 0). However, no building may be raised in a way that changes the skyline from any of the four cardinal directions.

Return the maximum total increase in building heights achievable under this constraint.

Example 1:

Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output: 35

Explanation: The building heights are shown in the center of the above image.

The skylines when viewed from each cardinal direction are drawn in red.

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],

[7, 4, 7, 7],

[9, 4, 8, 7],

[3, 3, 3, 3] ]

Example 2:

Input: grid = [[0,0,0],[0,0,0],[0,0,0]]

Output: 0

Explanation: Increasing the height of any building will result in the skyline changing.

Code

1

2

3

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int: