LC 554. 砖墙

题目描述

这是 LeetCode 上的 554. 砖墙 ，难度为 中等。

你的面前有一堵矩形的、由 n 行砖块组成的砖墙。

这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。

如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。

你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。

其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。

你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。

示例 1：

1
2
3
输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

输出：2

示例 2：

1
2
3
输入：wall = [[1],[1],[1]]

输出：3

提示：

  • n == wall.length
  • 1 <= n <= $10^4$
  • 1 <= wall[i].length <= $10^4$
  • 1 <= sum(wall[i].length) <= 2 * $10^4$
  • 对于每一行 i ，sum(wall[i]) 是相同的
  • 1 <= wall[i][j] <= $2^{31}$ - 1

哈希表

题目要求穿过的砖块数量最少，等效于通过的间隙最多。

我们可以使用「哈希表」记录每个间隙的出现次数，最终统计所有行中哪些间隙出现得最多，使用「总行数」减去「间隙出现的最多次数」即是答案。

如何记录间隙呢？直接使用行前缀记录即可。

就用示例数据来举 🌰 ：

image.png

  • 第 1 行的间隙有 [1,3,5]
  • 第 2 行的间隙有 [3,4]
  • 第 3 行的间隙有 [1,4]
  • 第 4 行的间隙有 [2]
  • 第 5 行的间隙有 [3,4]
  • 第 6 行的间隙有 [1,4,5]

对间隙计数完成后，遍历「哈希表」找出出现次数最多间隙 4，根据同一个间隙编号只会在单行内被统计一次，用总行数减去出现次数，即得到「最少穿过的砖块数」。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)$

关于是否需要考虑「溢出」的说明

类似的问题，在之前 题解 也说过，这里再提一下 ~

当 Java 发生溢出时，会直接转成负数来处理。因此对于本题不会影响正确性（不重复溢出的话）。

可以通过以下例子来体会：

1
2
3
4
5
6
7
8
9
10
{
    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 上是无法被正常执行的：

[]
1
2
3
4
5
6
7
8
9
10
{
    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
2
3
4
5
1 <= sum(wall[i]) <= 2 * 10^4

错写成了

1 <= sum(wall[i].length) <= 2 * 10^4

因为在给定下面两个条件的情况下：

1
2
1 <= n <= 10^4
1 <= wall[i].length <= 10^4

$1 <= sum(wall[i].length) <= 2 * 10^4$ 十分多余。

针对反例：

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

我用官方提供的代码，跑的也是 0，所以如果是以官方的代码为评测标准的话，用 long long 反而是 WA 了 🤣

最后

这是我们「刷穿 LeetCode」系列文章的第 No.554 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

哈希表

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！