LeetCode 554. 砖墙

2023-08-29 HGNULB 约 5 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 554. 砖墙

题意分析

一面墙由若干行砖砌成，每一行用一个数组给出各块砖的宽度，所有行的总宽度相同。要从墙顶画一条竖直的线到墙底，求这条线最少穿过多少块砖；如果线正好落在两块砖的接缝上，就不算穿过这两块砖；并且不允许沿着墙的最左或最右边界画。

第一个信号是「不能画在两侧边界」。如果允许，答案永远是 0，题目就没有意义了；这条限制在代码里的落点非常具体——每一行累加宽度时，必须在倒数第二块砖处停下，因为累加完最后一块得到的位置就是墙的右边界。

第二个信号更关键：竖线的位置和每一行是独立结算的。对某一行来说，只有「线落在这一行的某条内部缝上」和「线穿过这一行的某块砖」两种结果，不存在第三种。也就是说，任何一条竖线穿过的砖块数 = 总行数 − 这条线正好命中缝的行数。于是求「穿过砖块最少」完全等价于求「缝最多的那个横坐标」，把一个看起来要枚举位置再逐行判断的问题，变成了一个纯粹的计数问题。

边界情况有两个。一是每一行都只有一块砖（例如 [[1],[1],[1]]），此时全墙没有任何内部缝，任何一条线都得穿过所有行，答案就是行数。二是宽度可以累加得很大，行数最多 $10^4$、总宽度最多 $2^{31} - 1$，位置这个量的取值极其稀疏，不能用「按坐标开数组」的方式统计。

解法：统计内部缝位置

核心思路

竖线穿过某一行时只有两种结果：落在砖缝上，不穿砖；否则恰好穿过一块砖。因此「穿过的砖最少」等价于「同一位置命中的砖缝行数最多」。若某位置有 maxGap 行存在砖缝，总行数为 rows，答案就是 rows - maxGap。

每一行的内部砖缝可以用前缀宽度表示。依次累加该行砖块宽度，但不累加最后一块：前几个前缀和是内部缝的位置，全部砖块之和则是墙的右边界，题目不允许沿边界画线。用哈希表统计每个位置出现的次数，同时维护最大值。

循环不变量是：处理完若干行后，gaps[p] 等于这些行在位置 p 上的内部缝数量，maxGap 是所有已统计位置的最大计数。每行的砖宽都为正，所以该行的前缀和严格递增，同一位置在一行内不会被重复计数。若所有行都只有一块砖，哈希表为空、maxGap = 0，自然得到答案 rows。

解题步骤

创建哈希表 gaps，gaps[p] 表示位置 p 出现过多少条内部缝；初始化 maxGap = 0。

对每一行把 position 重置为 0，只遍历到倒数第二块砖。

累加当前砖宽得到一条内部缝的位置，将 gaps[position] 加一，并更新 maxGap。

所有行处理完后，返回 wall.size() - maxGap。

在样例中，位置 4 被 4 行的砖缝命中，总行数为 6，所以竖线只会穿过另外 2 行中的砖，答案为 2。

代码实现

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> gaps = new HashMap<>();
        int maxGap = 0;

        for (List<Integer> row : wall) {
            int position = 0;
            for (int i = 0; i < row.size() - 1; i++) {
                position += row.get(i);
                int count = gaps.getOrDefault(position, 0) + 1;
                gaps.put(position, count);
                maxGap = Math.max(maxGap, count);
            }
        }
        return wall.size() - maxGap;
    }
}

func leastBricks(wall [][]int) int {
    gaps := make(map[int]int)
    maxGap := 0
    for _, row := range wall {
        position := 0
        for i := 0; i < len(row)-1; i++ {
            position += row[i]
            gaps[position]++
            if gaps[position] > maxGap {
                maxGap = gaps[position]
            }
        }
    }
    return len(wall) - maxGap
}

复杂度分析

时间复杂度：$O(T)$，其中 T 是所有砖块的总数；每条内部缝只统计一次。

空间复杂度：$O(G)$，其中 G 是不同内部缝位置的数量，且 G <= T。

关键点总结

先做等价转换：最少穿砖数 = 总行数 - 最多命中砖缝的行数。

前缀宽度把不同分块方式下的砖缝映射到统一横坐标。

最后一个前缀和是右边界，必须排除；左边界 0 因为没有入表，也被自然排除。

坐标值域很大、实际出现位置很少，哈希表比按总宽度开数组更合适。

maxGap 从 0 开始即可覆盖「没有内部砖缝」的边界，无需特判。

易错点总结

把最后一块也累加会把墙的右边界算成所有行共享的缝，答案可能错误地变成 0。

position 必须在每一行开始时清零，否则不同各行的横坐标基准不一致。

最终应返回「行数减最大缝数」，不能减砖块总数，也不能直接返回 maxGap。

每行只有一块砖时没有内部缝，正确答案是行数，不是 0。

Java 更新首次出现的位置时要用 getOrDefault，否则 null 自动拆箱会抛异常。

相似题目

题目	难度	考察点
169. 多数元素	简单	出现次数过半的元素
347. 前 K 个高频元素	中等	计数后取前 K 大
447. 回旋镖的数量	中等	按距离分组计数
560. 和为 K 的子数组	中等	前缀和配哈希表计数
149. 直线上最多的点数	困难	按斜率分组求最大共线数