难度：【中等】
你的面前有一堵矩形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。
砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。
如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。
你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
示例：
输入: [[1,2,2,1], [3,1,2], [1,3,2], [2,4], [3,1,2], [1,3,1,1]]
输出: 2
解释:
提示：
每一行砖块的宽度之和应该相等，并且不能超过 INT_MAX。每一行砖块的数量在 [1,10,000] 范围内， 墙的高度在 [1,10,000] 范围内， 总的砖块数量不超过 20,000。
解题思路：
逐一遍历墙的每一行，对于每一块砖，我们将当前行遇到的所有砖头的宽度加起来得到 sum，如果这个 sum 在 map中没有出线过，我们创建一个初始 count 值为 1 的相应条目。如果 sum 已经存在于哈希表中，我们只需要给对应的 count 加一。
对于每一行，只考虑到倒数第二块砖头的 sum 值，因为最后一块砖头的右边界不是一个衔接处。
最后，从哈希表中找到最大的 count 值，用这个值求出垂直竖线穿过的最少砖块数。
代码实现：
class Solution {
public int leastBricks(List
<List
<Integer>> wall
) {
Map
<Integer,Integer> map
= new HashMap<>();
int sum
;
for(List
<Integer> nums
: wall
) {
sum
= 0;
for(int i
= 0;i
< nums
.size()-1;i
++) {
sum
+= nums
.get(i
);
map
.put(sum
,map
.getOrDefault(sum
,0)+1);
}
}
int n
= wall
.size();
int ans
= n
;
for (Integer value
: map
.values()) {
ans
= Math
.min(ans
,n
- value
);
}
return ans
;
}
}
复杂度分析
时间复杂度： O(n)。我们只会遍历每一块完整的砖块一次， n 是墙的所有砖的总数。空间复杂度： O(m)。 map 只包含最多 m 个记录，其中 m 是墙的宽度。
