首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >增加最大值以保持Java的城市天际线

增加最大值以保持Java的城市天际线
EN

Code Review用户
提问于 2018-05-03 10:42:47
回答 1查看 691关注 0票数 2

在二维数组网格中,每个值网格表示位于那里的建筑物的高度。我们可以增加任何数目的建筑物的高度,以任何数额(数额可以不同的建筑物)。0高度也被认为是一座建筑物。

最后,当从网格的所有四个方向(即顶部、底部、左侧和右侧)查看“天际线”时,必须与原始网格的天际线相同。从远处看,城市的天际线是所有建筑物形成的矩形的外部轮廓。请参阅下面的示例。

建筑物的高度可以增加的最大总和是多少?

代码语言:javascript
运行
复制
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:
  • 1< grid.length =网格0.length <= 50。
  • 所有的高度网格都在0,100范围内。
  • 网格中的所有建筑物都占据整个网格单元:也就是说,它们是1×1×1的网格矩形棱镜。

我的方法:

代码语言:javascript
运行
复制
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)是否有更好的方法来解决这个问题?

参考文献

EN

回答 1

Code Review用户

发布于 2018-05-03 11:43:21

  • 这里: for( int i= 0;i< ncols;i++ ){ int max = Integer.MIN_VALUE;for( int j= 0;jJ ) max = gridJ;} topBot我 = max;}您不需要额外的变量max作为引用。您只需使用topBot[i]作为引用(在创建数组时,int数组的元素将初始化为默认值0,而且由于建筑物的高度不能小于00是一个足够的初始值)。另外,检查if(max < grid[j][i]) (即使用<而不是<=)就足够了,因为如果两个值相等,则不需要分配变量。实际上,有一种更简洁的方法可以这样写: topBot我 = Math.max(topBot我,gridJ);在消除了局部变量max之后,您可以在一个循环中填充topBotleftRig:for (int i= 0;i< ncols;i++) { for (int j= 0;jJ);leftRigJ = Math.max(leftRigJ,gridJ);}
  • 在最后一个循环中,在内部min循环之外不需要for,因此在这个内环中声明它就足够了。将变量的范围缩小到所需的最小程度,可以使代码更容易阅读,因为在这种情况下,它会立即使变量在循环外不需要。
票数 2
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/193556

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档