> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/hash/tong-ji-pin-lv/brick-wall.md).

# Brick Wall

<https://leetcode.com/problems/brick-wall/description/>

> There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the**top**to the**bottom**and cross the**least**bricks.
>
> The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.
>
> If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.
>
> **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.**

## Thoughts

观察到遇到的缝最多的即我们要找的那条路。每个缝即一个位置。把缝隙位置存下来, 记下freq。freq最大的即所要找的路。

把墙数减去最大缝的缝数即所求。

## Code

```
class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> freq = new HashMap<>();
        int wallLen = 0;
        for (Integer b : wall.get(0)) {
            wallLen += b;
        }
        for (List<Integer> w : wall) {
            int pos = 0;
            for (Integer b : w) {
                pos += b;
                freq.put(pos, freq.getOrDefault(pos, 0) + 1);
            }
        }

        int max = 0;
        for (Integer pos : freq.keySet()) {
            if (pos != wallLen) {
                max = Math.max(max, freq.get(pos));
            }
        }
        return wall.size() - max;
    }
}
```

## Analysis

Errors:

1. 忘了把等于wallLen那条路抛去。

时间复杂度O(n). 空间O(n).