807 Max Increase to Keep City Skyline 保持城市天際線
Description:
There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.
A city's skyline is the the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.
We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a 0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.
Return the maximum total sum that the height of the buildings can be increased by without changing the city's skyline from any cardinal direction.
Example:
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.
Constraints:
n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100
題目描述:
在二維數(shù)組grid中，grid[i][j]代表位于某處的建筑物的高度。 我們被允許增加任何數(shù)量（不同建筑物的數(shù)量可能不同）的建筑物的高度。 高度 0 也被認(rèn)為是建筑物。
最后，從新數(shù)組的所有四個方向（即頂部，底部，左側(cè)和右側(cè)）觀看的“天際線”必須與原始數(shù)組的天際線相同。 城市的天際線是從遠處觀看時，由所有建筑物形成的矩形的外部輪廓。 請看下面的例子。
建筑物高度可以增加的最大總和是多少？
示例 :
輸入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
輸出： 35
解釋：
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]
從數(shù)組豎直方向（即頂部，底部）看“天際線”是：[9, 4, 8, 7]
從水平水平方向（即左側(cè)，右側(cè)）看“天際線”是：[8, 7, 9, 3]
在不影響天際線的情況下對建筑物進行增高后，新數(shù)組如下：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
說明:
1 < grid.length = grid[0].length <= 50。
grid[i][j] 的高度范圍是： [0, 100]。
一座建筑物占據(jù)一個grid[i][j]：換言之，它們是 1 x 1 x grid[i][j] 的長方體。
思路:
模擬
記錄下每一行每一列的最大值
取每個元素對應(yīng)列對應(yīng)行的最大值的較小值減去自身就是能增加的高度
時間復(fù)雜度為 O(mn), 空間復(fù)雜度為 O(max(m, n))
代碼:
C++:
class Solution
{
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid)
{
int result = 0, m = grid.size(), n = grid[0].size();
vector<int> r(m), c(n);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
r[i] = max(r[i], grid[i][j]);
c[j] = max(c[j], grid[i][j]);
}
}
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) result += min(r[i], c[j]) - grid[i][j];
return result;
}
};
Java:
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int result = 0, m = grid.length, n = grid[0].length, r[] = new int[m], c[] = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
r[i] = Math.max(r[i], grid[i][j]);
c[j] = Math.max(c[j], grid[i][j]);
}
}
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) result += Math.min(r[i], c[j]) - grid[i][j];
return result;
}
}
Python:
class Solution:
def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
return sum(min((r := [max(i) for i in grid])[i], (c := [max(i) for i in zip(*grid)])[j]) - grid[i][j] for i in range(len(grid)) for j in range(len(grid)))
