0554. Brick Wall

# 554. Brick Wall#

## 题目 #

There is a rectangular brick wall in front of you with `n` rows of bricks. The `ith` row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.

Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Given the 2D array `wall` that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.

Example 1:

``````Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
Output: 2

``````

Example 2:

``````Input: wall = [[1],[1],[1]]
Output: 3

``````

Constraints:

• `n == wall.length`
• `1 <= n <= 10^4`
• `1 <= wall[i].length <= 10^4`
• `1 <= sum(wall[i].length) <= 2 * 10^4`
• `sum(wall[i])` is the same for each row `i`.
• `1 <= wall[i][j] <= 2^31 - 1`

## 解题思路 #

• 既然穿过砖块中缝不算穿过砖块，那么穿过最少砖块数量一定是穿过很多中缝。按行遍历每一行的砖块，累加每行砖块宽度，将每行砖块“缝”的坐标存在 map 中。最后取出 map 中出现频次最高的缝，即为铅垂线要穿过的地方。墙高减去缝出现的频次，剩下的即为穿过砖块的数量。

## 代码 #

``````package leetcode

func leastBricks(wall [][]int) int {
m := make(map[int]int)
for _, row := range wall {
sum := 0
for i := 0; i < len(row)-1; i++ {
sum += row[i]
m[sum]++
}
}
max := 0
for _, v := range m {
if v > max {
max = v
}
}
return len(wall) - max
}
``````

Nov 25, 2022