题目

标题和出处

标题：砖墙

出处：554. 砖墙

难度

5 级

题目描述

要求

你的面前有一堵矩形的、由 $\text{n}$ 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和相等。

你现在要画一条自顶向下的、穿过最少砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 $\text{wall}$，该数组包含这堵墙的相关信息。其中，$\text{wall[i]}$ 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线穿过的砖块数量最少，并且返回穿过的砖块数量。

示例

示例 1：

输入：$\text{wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]}$
输出：$\text{2}$

示例 2：

输入：$\text{wall = [[1],[1],[1]]}$
输出：$\text{3}$

数据范围

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

解法

思路和算法

任意一条垂线在每一行都是穿过砖块或者从砖块的边缘经过，且穿过砖块的数量与从砖块的边缘经过的数量之和一定等于砖墙的行数 $n$。为了找到穿过最少砖块的垂线，应该找到经过最多的砖块边缘的垂线，砖墙的行数与该垂线经过的砖块边缘的数量之差即为穿过的砖块数量的最小值。

为了找到经过最多的砖块边缘的垂线，需要统计从砖墙左端开始的所有不同距离的砖块边缘的数量，并用哈希表记录所有距离对应的砖块边缘的数量。

对于砖墙的每一行，从左到右遍历每一块砖，并维护砖块宽度之和，砖块宽度之和即为当前砖块的右边缘与砖墙左端的距离。对于每一块砖，将其宽度加到砖块宽度之和中，并将更新后的砖块宽度之和在哈希表中的次数加 $1$。由于不能沿着墙的两个垂直边缘之一画线，因此每一行的最后一块砖不用遍历。

由于题目没有要求得到画线的位置，只要求得到穿过的砖块数量的最小值，因此在遍历结束砖墙的全部行之后，只需要从哈希表中得到砖块边缘数量的最大值，不需要得到砖块边缘与砖墙左端的距离。得到砖块边缘数量的最大值之后，计算砖墙的行数与砖块边缘数量的最大值之差，即为穿过的砖块数量的最小值。

代码

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int n = wall.size();
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        for (List<Integer> row : wall) {
            long sum = 0;
            int bricks = row.size();
            for (int i = 0; i < bricks - 1; i++) {
                sum += row.get(i);
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        int maxCount = 0;
        Set<Map.Entry<Long, Integer>> entries = map.entrySet();
        for (Map.Entry<Long, Integer> entry : entries) {
            int count = entry.getValue();
            maxCount = Math.max(maxCount, count);
        }
        return n - maxCount;
    }
}

复杂度分析

• 时间复杂度：$O(mn)$，其中 $m$ 是砖墙每一行的平均砖块数量，$n$ 是砖墙的行数。需要遍历砖墙中的每一行的除了最后一块砖的每块砖，并用哈希表记录每块砖的右边缘与砖墙左端的距离和次数。

• 空间复杂度：$O(mn)$，其中 $m$ 是砖墙每一行的平均砖块数量，$n$ 是砖墙的行数。需要使用哈希表记录每一行的除了最后一块砖的每块砖的右边缘与砖墙左端的距离和次数。