友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
554. 砖墙
你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。
你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
给你一个二维数组 wall，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
示例 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
提示：
-
n == wall.length -
1 <= n <= 104 -
1 <= wall[i].length <= 104 -
1 <= sum(wall[i].length) <= 2 * 104 -
对于每一行
i，sum(wall[i])是相同的 -
1 <= wall[i][j] <= 231 - 1
思路分析
使用前缀和，求解每一行的缝隙值大小，使用哈希存储缝隙值出现的次数。缝隙值出现次数最多的值，就是要求解的情况。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-03-11 22:11:47
*/
public int leastBricks(List<List<Integer>> wall) {
Map<Integer, Integer> sumToCountMap = new HashMap<>();
int result = 0;
for (List<Integer> walls : wall) {
int presum = 0;
for (int i = 0; i < walls.size() - 1; i++) {
presum += walls.get(i);
sumToCountMap.put(presum, sumToCountMap.getOrDefault(presum, 0) + 1);
result = Math.max(result, sumToCountMap.get(presum));
}
}
return wall.size() - result;
}