最大幅度增加以保持城市天际线

Question

我正在试图解决 LeetCode问题。

在本地测试算法时，我设法正确地找到了“水平”视图的“天际线”(“水平”=通过查看矩阵的列可以看到的视图)。

尽管对于“垂直”视图(“垂直”=通过查看矩阵的行可以看到的视图)，我在verticalView数组中的最后2个值不是正确的值，我也不明白为什么。

我添加了println来显示变量的值。

我不明白为什么当verticalView[2] = 8 ( i = 0, j = 2)、i = 2和j = 2时，verticalView[2]变成了0。

import java.util.Arrays;

class Solution {
    public static int maxIncreaseKeepingSkyline(int[][] grid) {
        int[] verticalView = new int[grid.length];
        int[] horizontalView =  new int[grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            verticalView[i] = 0;
            horizontalView[i] = 0;
            for (int j = 0; j < grid[0].length; j++) {
                boolean b = grid[i][j] > verticalView[j];
                System.out.println("verticalView[" + j + "] = " + verticalView[j]);

                if (grid[i][j] > verticalView[j] /* b */) verticalView[j] = grid[i][j];
                if (grid[i][j] > horizontalView[i]) horizontalView[i] = grid[i][j];

                System.out.println("grid[" + i + "][" + j + "] > verticalView[" + j + "] = " + b);
                System.out.println("grid[" + i + "][" + j + "] = " + grid[i][j]);
                System.out.println("verticalView[" + j + "] = " + verticalView[j]);
                System.out.println();
            }
        }
        System.out.println("Vertical view: " + Arrays.toString(verticalView));
        System.out.println("Horizontal view: " + Arrays.toString(horizontalView));

//        int[] verticalView = {9,4,8,7};
//        int[] horizontalView = {8,7,9,3};
        int sum = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                while (grid[i][j] < verticalView[j] & grid[i][j] < horizontalView[i]) {
                    grid[i][j]++;
                    sum++;
                }
            }
        }

//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                System.out.print(grid[i][j] + " ");
//            }
//            System.out.println();
//        }
        return sum;
    }

    public static void main(String[] args) {

        int[][] n = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3},{0, 3, 1, 0}};

        System.out.println("Solution: " + maxIncreaseKeepingSkyline(n));
    }
}

Answer 1

代码中的错误出现在：

verticalView[i] = 0;
horizontalView[i] = 0;

在java中，数组的默认值为零。

即使将值更新为0以外的值，也要将值更改为零。

简化问题解决办法：

import java.util.Arrays;

class Solution {
    public static int maxIncreaseKeepingSkyline(int[][] grid) {
        int[] verticalView = new int[grid.length];
        int[] horizontalView =  new int[grid[0].length];
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] > verticalView[j]) verticalView[j] = grid[i][j];
                if (grid[i][j] > horizontalView[i]) horizontalView[i] = grid[i][j];
            }
            
        }
        
        int sum = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                while (grid[i][j] < verticalView[j] & grid[i][j] < horizontalView[i]) {
                    grid[i][j]++;
                    sum++;
                }
            }
        }

        return sum;
    }

    public static void main(String[] args) {

        int[][] n = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3},{0, 3, 1, 0}};

        System.out.println("Solution: " + maxIncreaseKeepingSkyline(n));
    }
}

Answer 2

看起来不错！

我们也可以使用Math.max()来简化它，不过，没有什么重要的：

public class Solution {
    public static final int maxIncreaseKeepingSkyline(
        final int[][] grid
    ) {
        int[] rows = new int[grid.length];
        int[] cols = new int[grid.length];

        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid.length; col++) {
                rows[row] = Math.max(rows[row], grid[row][col]);
                cols[col] = Math.max(cols[col], grid[row][col]);
            }
        }

        int maxIncrease = 0;

        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid.length; col++) {
                maxIncrease += Math.min(rows[row], cols[col]) - grid[row][col];
            }
        }

        return maxIncrease;
    }
}