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

Question

我正在尝试解决“保持城市天际线的最大增加” LeetCode 问题。

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

虽然，对于“垂直”视图（“垂直”=通过查看矩阵行看到的视图），我在 verticalView 数组中的最后两个值不是正确的，我不明白为什么。

我添加了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));
    }
}

标签： javaalgorithm

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