java - 最大增加以保持城市天际线

Question

我正在尝试解决 "Max Increase to Keep City Skyline" LeetCode 问题。
在本地测试算法，我设法正确找到了“水平” View 的“天际线”(“水平”=您通过查看矩阵列看到的 View )。
虽然，对于“垂直” View (“垂直”=您通过查看矩阵行看到的 View )，我在 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中数组的默认值为零。
即使将值更新为零以外的值，您也将其更改为零。
问题的简化解决方案:

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));
    }
}