LC 554. 砖墙

题目描述

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

你的面前有一堵矩形的、由 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 <= 10^4$
• $1 <= wall[i].length <= 10^4$
• $1 <= sum(wall[i].length) <= 2 \times 10^4$
• 对于每一行 i，sum(wall[i]) 是相同的
• $1 <= wall[i][j] <= 2^{31} - 1$

---

哈希表

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

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

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

就用示例数据来举 🌰 ：

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

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

Java 代码：

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int n = wall.size(), ans = n;
        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 掉最后一个
        }
        for (int u : map.keySet()) ans = Math.min(ans, n - map.get(u));
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        int n = wall.size(), ans = n;
        unordered_map<int, int> map;
        for (int i = 0, sum = 0; i < n; i++, sum = 0) {
            for (int cur : wall[i]) {
                sum += cur;
                map[sum]++;
            }
            map[sum]--;
        }
        for (auto& u : map) ans = min(ans, n - u.second);
        return ans;
    }
};

Python 代码：

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n, ans = len(wall), len(wall)
        mapping = defaultdict(int)
        sumv = 0
        for i in range(n):
            for cur in wall[i]:
                sumv += cur
                mapping[sumv] += 1 
            mapping[sumv] -= 1     
            sumv = 0
        for u in mapping:
            ans = min(ans, n - mapping[u])
        return ans

TypeScript 代码：

function leastBricks(wall: number[][]): number {
    let n = wall.length, ans = n;
    const map: Map<number, number> = new Map();
    for (let i = 0, sum = 0; i < n; i++, sum = 0) {
        for (const cur of wall[i]) {
            sum += cur;
            if (map.has(sum)) map.set(sum, map.get(sum) + 1);    
            else map.set(sum, 1);
        }
        map.set(sum, map.get(sum) - 1);
    }
    map.forEach((value: number) => {
        ans = Math.min(ans, n - value);
    });
    return ans;
};

• 时间复杂度：记所有砖块数量为 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 * 10^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 原题链接和其他优选题解。