在二维数组网格中,每个值网格我表示位于那里的建筑物的高度。我们可以增加任何数目的建筑物的高度,以任何数额(数额可以不同的建筑物)。0高度也被认为是一座建筑物。
最后,当从网格的所有四个方向(即顶部、底部、左侧和右侧)查看“天际线”时,必须与原始网格的天际线相同。从远处看,城市的天际线是所有建筑物形成的矩形的外部轮廓。请参阅下面的示例。
建筑物的高度可以增加的最大总和是多少?
Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[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] ]
The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]
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] ]
Notes:
我的方法:
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int nrows = grid.length;
int ncols = grid[0].length;
int [] leftRig = new int[nrows];
int [] topBot = new int[ncols];
//Filling topBot
for( int i = 0; i < ncols; i++ )
{
int max = Integer.MIN_VALUE;
for( int j = 0; j < nrows; j++ )
{
if( max <= grid[j][i] )
max = grid[j][i];
}
topBot[i] = max;
}
//Filling leftRig
for( int k = 0; k < nrows; k++ )
{
int max = Integer.MIN_VALUE;
for( int l = 0; l < ncols; l++ )
{
if( max <= grid[k][l] )
max = grid[k][l];
}
leftRig[k] = max;
}
int count = 0;
int min = 0;
//Enumerating the minimum height to be added
for( int i = 0; i < nrows; i++ )
{
for( int j = 0; j < ncols; j++ )
{
min = Math.min(leftRig[i],topBot[j]);
count += min - grid[i][j];
}
}
return count;
}
}
时间复杂度: O(n^2)
空间复杂性: O(n)
时间复杂度: O(n)空间复杂度: O(n)
关于上面的代码片段,我有以下问题:
1)如何提高代码的时间和空间复杂度?
( 2)是否有更好的方法(较少的代码行、更好的数据结构)可用于改进代码?
( 3)是否有更好的方法来解决这个问题?
发布于 2018-05-03 11:43:21
max
作为引用。您只需使用topBot[i]
作为引用(在创建数组时,int
数组的元素将初始化为默认值0
,而且由于建筑物的高度不能小于0
,0
是一个足够的初始值)。另外,检查if(max < grid[j][i])
(即使用<
而不是<=
)就足够了,因为如果两个值相等,则不需要分配变量。实际上,有一种更简洁的方法可以这样写: topBot我 = Math.max(topBot我,gridJ);在消除了局部变量max
之后,您可以在一个循环中填充topBot
和leftRig
:for (int i= 0;i< ncols;i++) { for (int j= 0;jJ);leftRigJ = Math.max(leftRigJ,gridJ);}min
循环之外不需要for
,因此在这个内环中声明它就足够了。将变量的范围缩小到所需的最小程度,可以使代码更容易阅读,因为在这种情况下,它会立即使变量在循环外不需要。https://codereview.stackexchange.com/questions/193556
复制相似问题