题目描述
这是 LeetCode 上的 554. 砖墙。
Tag : 「哈希表」
你的面前有一堵矩形的、由 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 复制代码
示例 2：
输入：wall = [[1],[1],[1]] 输出：3 复制代码
提示：
- n == wall.length
- 1 <= n <= 10410^4104
- 1 <= wall[i].length <= 10410^4104
- 1 <= sum(wall[i].length) <= 2 * 10410^4104
- 对于每一行 i ，sum(wall[i]) 是相同的
- 1 <=
wall[i][j]<= 2312^{31}231 - 1
哈希表
题目要求穿过的砖块数量最少，等效于通过的间隙最多。
我们可以使用「哈希表」记录每个间隙的出现次数，最终统计所有行中哪些间隙出现得最多，使用「总行数」减去「间隙出现的最多次数」即是答案。
如何记录间隙呢？直接使用行前缀记录即可。
就用示例数据来举 🌰 ：
- 第 1 行的间隙有
[1,3,5] - 第 2 行的间隙有
[3,4] - 第 3 行的间隙有
[1,4] - 第 4 行的间隙有
[2] - 第 5 行的间隙有
[3,4] - 第 6 行的间隙有
[1,4,5]
对间隙计数完成后，遍历「哈希表」找出出现次数最多间隙 4，根据同一个间隙编号只会在单行内被统计一次，用总行数减去出现次数，即得到「最少穿过的砖块数」。
代码：
class Solution { public int leastBricks(List<List<Integer>> wall) { int n = wall.size(); Map<Integer, Integer> map = new HashMap<>(); for (int i = 0, sum = 0; i < n; i++, sum = 0) { for (int cur : wall.get(i)) { sum += cur; map.put(sum, map.getOrDefault(sum, 0) + 1); } map.remove(sum); // 不能从两边穿过，需要 remove 掉最后一个 } int ans = n; for (int u : map.keySet()) { int cnt = map.get(u); ans = Math.min(ans, n - cnt); } return ans; } } 复制代码
- 时间复杂度：记所有砖块数量为
n，所有砖块都会被扫描。复杂度为 O(n)O(n)O(n) - 空间复杂度：O(n)O(n)O(n)
关于是否需要考虑「溢出」的说明
类似的问题，在之前 题解 也说过，这里再提一下 ~
当 Java 发生溢出时，会直接转成负数来处理。因此对于本题不会影响正确性（不重复溢出的话）。
可以通过以下例子来体会：
{ System.out.println(Integer.MIN_VALUE); // -2147483648 int a = Integer.MAX_VALUE; System.out.println(a); // 2147483647 a += 1; System.out.println(a); // -2147483648 a -= 1; System.out.println(a); //2147483647 } 复制代码
这意味着，如果我们在运算过程中如果只涉及「纯加减运算」，而不涉及「乘除」、「取最大值/最小值」和「数值大小判断」的话，Java 是不需要使用 Long 来确保正确性的，因为最终溢出会被转化回来。
按道理，CPP 本身对于 int 溢出的转化处理也是一样的。
但在 LC 上的 CPP 发生溢出时，不会直接转成负数来处理，而是直接抛出异常。因此同样的代码在 LC 上是无法被正常执行的：
{ cout << INT_MIN << endl; //-2147483648 int a = INT_MAX; cout << a << endl; // 2147483647 a += 1; // 溢出报错 cout << a << endl; a -= 1; cout << a << endl; } 复制代码
这是一般性的，对于 LC 上的同一道题，Java 不需要处理溢出，CPP 需要处理的原因。
其实对应到本题，我这里不使用 long long，是因为猜想「题目」中的条件写错了：
1 <= sum(wall[i]) <= 2 * 10^4 错写成了 1 <= sum(wall[i].length) <= 2 * 10^4 复制代码
因为在给定下面两个条件的情况下：
1 <= n <= 10^4 1 <= wall[i].length <= 10^4 复制代码
1<=sum(wall[i].length)<=2∗1041 <= sum(wall[i].length) <= 2 * 10^41<=sum(wall[i].length)<=2∗104 十分多余。
针对反例：
[ [2147483647,2147483647,2147483647,2147483647,1,2], [2,2147483647,2147483647,2147483647,2147483647,1] ] 复制代码
我用官方提供的代码，跑的也是 0，所以如果是以官方的代码为评测标准的话，用 long long 反而是 WA 了 🤣
最后
这是我们「刷穿 LeetCode」系列文章的第 No.554 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
