LeetCode「Max Increase to Keep City Skyline」算法调试求助

我一眼就揪出了问题的根源——你在第一个双层循环的外层循环开头做了完全没必要的操作：每次遍历新行（i递增）时，都把verticalView[i]和horizontalView[i]强制重置为0，这直接把之前计算好的列最大值给覆盖了！

具体错误分析 #

你的verticalView数组是用来存储每一列的最大值（对应题目中「上下视角」的天际线），它的长度等于矩阵的列数（grid[0].length）。但在你的外层循环里：

for (int i = 0; i < grid.length; i++) {
    verticalView[i] = 0; // 这里就是bug所在！
    horizontalView[i] = 0;
    // ... 内层循环逻辑
}

举个例子：当i=0时，你成功把verticalView[2]设为8（对应第一行第三列的数值）；但当i=2时，这段代码会把verticalView[2]重新赋值为0，直接覆盖了之前的正确值——这就是你看到「到i=2、j=2时该值变为0」的原因！

而且这段代码还有潜在的数组越界风险：如果你的矩阵不是方阵（行数列数不一致），比如3行4列的矩阵，当i=3时访问verticalView[3]没问题，但如果是4行3列，i=3时访问verticalView[3]就会直接抛出异常，因为verticalView的长度只有3。

修正方案 #

我们需要把数组初始化和循环内的错误重置操作彻底分开：

1. 先一次性把两个数组初始化为全0，不需要在循环里逐行重置；
2. 外层循环遍历每一行，内层循环遍历每一列，分别更新对应列的最大值（verticalView[j]）和对应行的最大值（horizontalView[i]）。

修正后的核心循环代码如下：

// 先初始化两个数组为全0，一次性搞定
int[] verticalView = new int[grid[0].length];
int[] horizontalView = new int[grid.length];
Arrays.fill(verticalView, 0);
Arrays.fill(horizontalView, 0);

for (int i = 0; i < grid.length; i++) {
    // 移除这里的verticalView[i] = 0和horizontalView[i] = 0！
    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];
        // 你的调试打印语句可以保留，方便验证
    }
}

额外优化建议 #

另外，你计算总和的while循环可以简化成一步到位的数学计算，不用逐次累加：

int sum = 0;
for (int i = 0; i < grid.length; i++) {
    for (int j = 0; j < grid[0].length; j++) {
        // 每个位置能增加到的最大值，是该行和该列天际线的最小值
        int maxPossible = Math.min(horizontalView[i], verticalView[j]);
        sum += maxPossible - grid[i][j];
    }
}

这样代码更简洁高效，也避免了循环累加的冗余操作。

验证结果 #

用你提供的测试用例{{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3},{0, 3, 1, 0}}，修正后：

• verticalView（列最大值）会正确输出[9,4,8,7]
• horizontalView（行最大值）会正确输出[8,7,9,3]
• 最终sum的结果是35，和题目预期完全一致。

内容的提问来源于stack exchange，提问作者Fabio Cirelli