某大厂员工：有个很菜的同事，去了体制内像他这样有学历没技术的，去体制内，是最不浪费个人优势的，能完美避开自己的短处!

面试题：砖墙

砖墙这题，最容易写歪的地方是去“画线”。

一看题目说从上往下画一条竖线，很多人第一反应就是模拟墙的每一列，看这条线穿过几块砖。这个方向我一般直接不信。砖宽可能很大，真按坐标一格一格扫，代码看着勤快，实际就是在给自己挖坑。

这题真正要看的，不是线穿过了多少块砖，而是线有没有刚好卡在砖缝上。

比如一行砖是：

[1, 2, 2, 1]

从左往右算砖缝位置：

1, 3, 5

注意最后那个墙的右边界不能算。题目不允许线贴着墙边画，不然直接一条线从最右边下去，穿过 0 块砖，这题就没意义了。

所以每一行只需要统计“内部砖缝”的位置。哪一个位置出现次数最多，说明竖线画在这里，能避开的砖最多。

最后答案就是：

总行数 - 出现次数最多的砖缝数

这地方有个坑，别把“砖块宽度”当成 key，key 应该是“前缀和位置”。

我会这么写：

import java.util.HashMap;
import java.util.List;
import java.util.Map;

publicclassBrickWallCounter{

publicintleastBricks(List<List<Integer>> wall){
        Map<Integer, Integer> gapCount = new HashMap<>();
int bestGap = 0;

for (List<Integer> row : wall) {
int pos = 0;

// 最后一块砖的右边界不能统计，所以只扫到 size - 1
for (int i = 0; i < row.size() - 1; i++) {
                pos += row.get(i);

int times = gapCount.getOrDefault(pos, 0) + 1;
                gapCount.put(pos, times);

if (times > bestGap) {
                    bestGap = times;
                }
            }
        }

return wall.size() - bestGap;
    }
}

这段代码里我最在意的是这个循环边界：

for (int i = 0; i < row.size() - 1; i++)

这比后面再判断“是不是最后一个位置”要干净。很多 bug 就是从多算了墙的最右边界开始的。尤其是测试样例比较弱的时候，你还以为自己过了，换一组全是单块砖的墙，结果就露馅了。

比如：

[
  [3],
  [3],
  [3]
]

每一行都没有内部砖缝。这个时候 gapCount 为空，bestGap 还是 0，结果就是 3。

意思也对：你不管怎么画，都会穿过 3 块砖。

再看一个稍微正常点的：

[
  [1, 2, 2, 1],
  [3, 1, 2],
  [1, 3, 2],
  [2, 4],
  [3, 1, 2],
  [1, 3, 1, 1]
]

内部砖缝位置大概会被统计成这样：

位置 1：出现 3 次
位置 2：出现 1 次
位置 3：出现 3 次
位置 4：出现 4 次
位置 5：出现 2 次

最多的是位置 4，出现了 4 次。总共有 6 行，所以最少穿过：

6 - 4 = 2

这题的复杂度也比较舒服。每块砖最多扫一次，时间复杂度是 O(n)，这里的 n 是所有砖块数量。空间复杂度取决于不同砖缝位置的数量，最坏也是 O(n)。

这类题别急着模拟过程。题目让你画线，不代表代码里真要画线。线只是表象，真正能减少穿砖数的，是每一行砖缝重合的位置。

把这个位置数清楚，题就结束了。