垂直、水平方向观看楼层天际线不变情况下能增加的建筑物高度最大总和

原题如下：

解题代码如下：

public class test {
    public static void main(String[] args) {
        int [][] grid = {{3,0,8,4},{2,4,5,7},{9,2,6,3},{0,3,1,0}};
        int maxY = 0;
        int maxX = 0;
        int count = 0;
        for(int i=0;i<grid.length;i++) {
            if(maxX<grid[i].length) {
                maxX = grid[i].length;
            }
        }
        maxY = grid.length;
        int y[] = new int [maxX];//竖直方向
        int x[] = new int [maxY];//水平方向
        //求出竖直方向天际线
        for(int i=0;i<maxX;i++) {
            int max = 0;
            for(int j=0;j<maxY;j++) {
                if(grid[j].length>i) {
                    if(grid[j][i]>max) {
                        max = grid[j][i];
                    }
                }
            }
            y[i] = max;
        }
        //求出水平方向天际线
        for(int i=0;i<maxY;i++) {
            int max = 0;
            for(int j=0;j<grid[i].length;j++) {
                if(grid[i][j]>max) {
                    max = grid[i][j];
                }
            }
            x[i]=max;
        }
        //求出增加层数总和及改变后的楼层数组
        for(int i=0;i<maxY;i++) {
            for(int j=0;j<grid[i].length;j++) {
                count += (x[i]<y[j]?x[i]:y[j])-grid[i][j];
                grid[i][j] = x[i]<y[j]?x[i]:y[j];
            }
        }
        //输出
        System.out.println(count);
        System.out.print("从数组垂直方向看天际线是:");
        for(int i=0;i<maxX;i++) {
            System.out.print(y[i]+" ");
        }
        System.out.println();
        System.out.print("从数组水平方向看天际线是:");
        for(int i=0;i<maxY;i++) {
            System.out.print(x[i]+" ");
        }
        System.out.println("
gridNew=");
        for(int i=0;i<maxY;i++) {
            for(int j=0;j<grid[i].length;j++) {
                System.out.print(grid[i][j]+" ");
            }
            System.out.println();
        }
    }
}

算法解析：

maxX为二维数组x轴最大长度，因为二维数组中每个一维长度可以不等，而竖直方向天际线的个数需要取x轴最大值个数；maxY 为y轴长度，水平方向天际线个数为y轴长度。

y存储竖直方向天际线，x存储水平方向天际线，count存储可以增加的建筑物高度总和。

竖直天际线就是二维数组每条y轴中的最大值，水平天际线就是每条x轴的最大值，需要注意的是由于数组一维长度不一定相等，在求竖直天际线的时候需要判断。

运行结果：

修改条件：

运行结果：

注意：数组一维和二维都不是固定的，因为一个城市的楼层不可能固定，所以在算法设计阶段应该考虑清楚。