554. 砖墙

554. 砖墙

题目描述

你的面前有一堵矩形的砖墙，墙由若干行砖块组成。

每块砖的宽度不同，但高度都相同。你的目标是在这堵墙上画一条 从上到下的垂直线，使得这条线 穿过的砖块数量最少。

如果你的线恰好沿着某些砖块的边缘经过，那么这不算穿过砖块。

你不能沿着墙的最左边缘或最右边缘画线，因为那样等于一块砖都不穿过，题目不允许。

给你一个二维数组 wall，其中 wall[i] 表示第 i 行砖块的宽度列表，返回你画的这条线 最少穿过的砖块数。

示例 1

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

示例 2

text
输入：wall = [[1],[1],[1]]
输出：3

约束

  • 1 <= wall.length <= 10^4
  • 1 <= wall[i].length <= 10^4
  • 1 <= sum(wall[i].length) <= 2 * 10^4
  • 1 <= wall[i][j] <= 2^31 - 1
  • 每一行砖块的总宽度都相同

核心思路

这题表面上在问：

画哪条竖线，能让穿过的砖块数最少？

但换个角度想就会更简单：

如果一条竖线经过很多行砖块的“边缘”，那它真正穿过的砖块就会更少。

所以这题本质上是在找：

  • 哪个“砖块边缘位置”出现的次数最多

假设墙一共有 rows 行：

  • 如果某个位置有 maxEdges 行都在这里结束一块砖
  • 那么我们把线画在这里
  • 就有 maxEdges 行不用穿砖
  • 剩下必须穿过的砖块数就是：
ts
rows - maxEdges

这题至少有两种常见做法：

  • 解法一：哈希表统计每个边缘位置出现次数（推荐）
  • 解法二：排序统计所有边缘位置

解法一：哈希表统计边缘位置

这是这题最经典、最推荐掌握的做法。

思路拆解

对于每一行砖块，我们从左往右累加宽度，就能得到这一行里所有内部边缘的位置。

比如一行是：

text
[1, 2, 2, 1]

那么边缘位置就是：

  • 第一块结束：1
  • 第二块结束：1 + 2 = 3
  • 第三块结束：1 + 2 + 2 = 5

最后总宽度 6 对应的是墙最右边缘，不能算。

所以这一行贡献的内部边缘位置是：

text
1, 3, 5

我们把所有行的这些内部边缘位置都统计起来，哪个位置出现次数最多，答案就是：

ts
wall.length - maxCount

为什么不能统计最后一块的结束位置？

因为最后一块的结束位置就是整堵墙的最右边缘。

题目明确说了：

  • 不能沿最左边缘画
  • 也不能沿最右边缘画

所以每一行都只能统计到 倒数第二块 为止。

这也是这题最容易写错的地方。

一步一步写出算法

第一步：准备哈希表

我们用 Map<number, number> 统计：

  • 某个边缘位置出现了多少次
ts
const edgeCount = new Map<number, number>()

第二步：逐行扫描，累加边缘位置

对每一行：

  • 用 sum 记录当前位置
  • 累加到每块砖结束的位置
  • 但最后一块不统计
ts
for (const row of wall) {
    let sum = 0
    for (let i = 0; i < row.length - 1; i++) {
        sum += row[i]
        edgeCount.set(sum, (edgeCount.get(sum) ?? 0) + 1)
    }
}

第三步：找出最大边缘重合次数

ts
let maxCount = 0
for (const count of edgeCount.values()) {
    maxCount = Math.max(maxCount, count)
}

第四步：计算答案

ts
return wall.length - maxCount

如果所有行都只有一块砖，那么 edgeCount 会一直为空，maxCount = 0，答案就是 wall.length。

这正好符合题意。

代码实现（TypeScript）

ts
function leastBricks(wall: number[][]): number {
    const edgeCount = new Map<number, number>()

    for (const row of wall) {
        let sum = 0
        for (let i = 0; i < row.length - 1; i++) {
            sum += row[i]
            edgeCount.set(sum, (edgeCount.get(sum) ?? 0) + 1)
        }
    }

    let maxCount = 0
    for (const count of edgeCount.values()) {
        maxCount = Math.max(maxCount, count)
    }

    return wall.length - maxCount
}

复杂度分析

  • 设所有行砖块总数为 n
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

因为我们基本只遍历了所有砖块一次，并用哈希表保存内部边缘位置。

这一解法的优缺点

优点：

  • 思路最直接
  • 代码最短
  • 是这题标准解法

缺点：

  • 需要想到“最少穿砖 = 最多对齐边缘”这个转换

解法二：排序统计所有边缘位置

这个做法本质上和哈希统计一样，只是把“计数”换成了“先收集，再排序统计连续段”。

思路拆解

我们还是先把所有内部边缘位置都找出来。

比如收集后得到：

text
[1, 3, 5, 3, 4, 1, 4, 2, 3, 1, 4, 1, 3, 4]

如果我们把它排序：

text
[1, 1, 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5]

那么：

  • 某个数字连续出现多少次
  • 就表示某个边缘位置出现了多少次

于是我们只要找出排序后最长的连续相同段长度即可。

最后答案同样是：

ts
wall.length - maxCount

一步一步写出算法

第一步：收集所有内部边缘位置

ts
const edges: number[] = []

for (const row of wall) {
    let sum = 0
    for (let i = 0; i < row.length - 1; i++) {
        sum += row[i]
        edges.push(sum)
    }
}

第二步：排序

ts
edges.sort((a, b) => a - b)

第三步：扫描相同元素的最长连续段

ts
let maxCount = 0
let currentCount = 0
let previous = -1

for (const edge of edges) {
    if (edge === previous) {
        currentCount++
    } else {
        currentCount = 1
        previous = edge
    }
    maxCount = Math.max(maxCount, currentCount)
}

第四步：返回答案

ts
return wall.length - maxCount

如果 edges 为空，maxCount 会保持 0，答案也是正确的。

代码实现（TypeScript）

ts
function leastBricks(wall: number[][]): number {
    const edges: number[] = []

    for (const row of wall) {
        let sum = 0
        for (let i = 0; i < row.length - 1; i++) {
            sum += row[i]
            edges.push(sum)
        }
    }

    edges.sort((a, b) => a - b)

    let maxCount = 0
    let currentCount = 0
    let previous = -1

    for (const edge of edges) {
        if (edge === previous) {
            currentCount++
        } else {
            currentCount = 1
            previous = edge
        }
        maxCount = Math.max(maxCount, currentCount)
    }

    return wall.length - maxCount
}

复杂度分析

  • 设所有内部边缘总数为 m
  • 收集边缘：O(m)
  • 排序：O(m log m)
  • 扫描：O(m)
  • 总时间复杂度：O(m log m)
  • 空间复杂度：O(m)

相比第一种哈希表做法，这个方法主要慢在排序。

这一解法的优缺点

优点：

  • 不依赖哈希计数逻辑
  • 对“统计重复值”这种思路更统一

缺点：

  • 需要排序
  • 不如哈希表解法高效

两种解法对比

解法时间复杂度空间复杂度特点
哈希表统计边缘O(n)O(n)标准解法，最推荐
排序统计边缘O(n log n)O(n)思路也直观，但稍慢

如果你是为了面试或者刷题效率，建议优先记第一种做法。

手动模拟一遍

以题目示例：

text
wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

为例。

第 1 行：[1,2,2,1]

内部边缘：

text
1, 3, 5

第 2 行：[3,1,2]

内部边缘：

text
3, 4

第 3 行：[1,3,2]

内部边缘：

text
1, 4

第 4 行：[2,4]

内部边缘：

text
2

第 5 行：[3,1,2]

内部边缘：

text
3, 4

第 6 行：[1,3,1,1]

内部边缘：

text
1, 4, 5

把这些都统计起来：

  • 1 出现 3 次
  • 2 出现 1 次
  • 3 出现 3 次
  • 4 出现 4 次
  • 5 出现 2 次

最多的是位置 4，出现了 4 次。

说明如果竖线画在位置 4：

  • 有 4 行正好沿着边缘走
  • 只有 6 - 4 = 2 行会真正穿过砖块

所以答案是：

text
2

面试时最容易错的点

1. 最右边缘不能统计

这是这题最容易错的点。

比如一行总宽度是 6，最后累加到 6 的那个位置不能加入统计。

所以循环一定要写成：

ts
for (let i = 0; i < row.length - 1; i++) {
    ...
}

而不是遍历到最后一块。

2. 不要真的去模拟“这条线穿过了哪些砖”

直接模拟一条线穿砖，会很难写，也完全没有必要。

应该先做思维转换：

  • 最少穿砖
  • 等价于最多经过砖缝

3. 边缘位置可能很大

砖块宽度最大可以到 2^31 - 1，不过在 JavaScript / TypeScript 的 number 范围里，这题正常处理没问题。

4. 如果每行只有一块砖怎么办？

这种情况下没有任何“内部边缘”。

于是：

  • maxCount = 0
  • 答案就是总行数 wall.length

这正好表示：

  • 不管你怎么画
  • 都必须穿过每一行唯一的一块砖

一句话总结

这题的本质是：

不要找“哪条线穿砖最少”，而要找“哪条线经过的砖块边缘最多”。

  • 想写最优解：用 哈希表统计边缘位置
  • 想换个统计方式理解：用 排序后数重复值

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个版本：

ts
function leastBricks(wall: number[][]): number {
    const edgeCount = new Map<number, number>()

    for (const row of wall) {
        let sum = 0
        for (let i = 0; i < row.length - 1; i++) {
            sum += row[i]
            edgeCount.set(sum, (edgeCount.get(sum) ?? 0) + 1)
        }
    }

    let maxCount = 0
    for (const count of edgeCount.values()) {
        maxCount = Math.max(maxCount, count)
    }

    return wall.length - maxCount
}

因为这个版本：

  • 思路最清晰
  • 代码最短
  • 时间复杂度最优
  • 是这题标准模板