---

0554. 砖墙

• 标签：数组、哈希表
• 难度：中等

题目链接

• 0554. 砖墙 - 力扣

题目大意

描述：

你的面前有一堵矩形的、由 $n$ 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 $wall$，该数组包含这堵墙的相关信息。其中，$wall[i]$ 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少，并且返回 穿过的砖块数量。

要求：

返回穿过的砖块数量的最小值。

说明：

• $n == wall.length$。
• $1 \le n \le 10^4$。
• $1 \le wall[i].length \le 10^4$。
• $1 \le sum(wall[i].length) \le 2 \times 10^4$。
• 对于每一行 $i$，$sum(wall[i])$ 是相同的。
• $1 \le wall[i][j] \le 2^{31} - 1$。

示例：

• 示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

• 示例 2：

输入：wall = [[1],[1],[1]]
输出：3

解题思路

思路 1：哈希表统计边缘位置

思路 1：算法描述

要使得穿过的砖块数量最少，我们需要让垂线尽可能多地穿过砖块之间的缝隙。

核心思路：

• 对于每一行，计算每个砖块右边缘的位置（前缀和），这些位置就是可以穿过缝隙的位置。
• 使用哈希表统计每个位置有多少行在这个位置有缝隙。
• 最终答案 = 总行数 - 最多行数在同一个位置有缝隙。

注意：不能沿着墙的两端画线，所以不考虑总宽度位置。

算法步骤：

1. 遍历每一行砖块。
2. 对于每一行，计算前缀和（每个砖块右边缘的位置）。
3. 使用哈希表 $edge\_count$ 统计每个边缘位置出现的次数（不包括最后一块砖的右边缘）。
4. 找到出现次数最多的边缘位置 $max\_edges$。
5. 返回 $rows - max\_edges$。

思路 1：代码

from collections import defaultdict

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        # 统计每个位置有多少行有缝隙
        edge_count = defaultdict(int)
        
        # 遍历每一行
        for row in wall:
            prefix_sum = 0
            # 计算每个砖块右边缘的位置（不包括最后一块砖的右边缘）
            for i in range(len(row) - 1):
                prefix_sum += row[i]
                edge_count[prefix_sum] += 1
        
        # 如果没有缝隙，返回总行数
        if not edge_count:
            return len(wall)
        
        # 找到最多行数在同一个位置有缝隙
        max_edges = max(edge_count.values())
        
        # 最少穿过的砖块数 = 总行数 - 最多行数在同一个位置有缝隙
        return len(wall) - max_edges

思路 1：复杂度分析

• 时间复杂度：$O(n \times m)$，其中 $n$ 是行数，$m$ 是平均每行的砖块数。需要遍历所有砖块。
• 空间复杂度：$O(w)$，其中 $w$ 是墙的总宽度。哈希表最多存储 $w$ 个不同的边缘位置。