题目描述

题目链接:554. 砖墙 - 力扣（LeetCode） (leetcode-cn.com)

你的面前有一堵矩形的、由 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

题目中要求，通过的砖块最少。可以反过来考虑，如果垂线经过间隔则不通过砖块，所以求通过的砖块最少，可以转化为通过的间隔最多。

如第一个例子

砖块分别为:

• 砖块[1,2,2,1] 间隔 [1,3,5]

• 砖块[3,1,2] 间隔[3,4]

• 砖块[1,3,2] 间隔[1,4]

• 砖块[2,4] 间隔[2]

• 砖块[3,1,2] 间隔[3,4]

• 砖块[1,3,1,1] 间隔[1,4,5]

此时，垂线从间隔4处通过的砖块最少

可以考虑使用hash table来计算，先对间隔计数，然后遍历hash table找到间隔出现最多的

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int height = wall.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < height; i++) {
            int sum = 0;
            // 获取每个砖块的长度，计算出间隔的长度
            for (int brick : wall.get(i)) {
                sum += brick;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
            // 只计算中间的间隔，不能从两边穿过，需要 remove 掉最后一个
            map.remove(sum); 
        }
        int res = height;
        // 遍历 获取每个间隔出现的次数，用高度相减，就是通过砖块的数量
        for (int space : map.keySet()) {
            int count = map.get(space);
            res = Math.min(res, height - count);
        }
        return res;
    }
}