LeetCode 554. 砖墙

2023-08-29 HGNULB 约 4 分钟

文章信息 6 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 10-20 华为

标签

数组 哈希表

题目描述

✅ 554. 砖墙

题意分析

每行砖块的总宽度相同，要在墙内选一个横坐标画竖线，使穿过的砖最少。竖线经过砖缝不算穿砖，但不能沿墙的左右外边界画线。

解法：统计内部缝位置

核心思路

[!blue]

固定一个横坐标，竖线在每行要么落在内部砖缝上，要么穿过一块砖。因此，穿砖数等于总行数减去这个坐标上有砖缝的行数，问题转为寻找出现次数最多的内部砖缝坐标。

从每行左端开始累加砖宽，每个前缀和就是当前砖的右边缘。只累计到倒数第二块，便排除了墙的右边界；左边界 0 也不记录。砖宽均为正，同一行的前缀和严格递增，所以一个坐标的计数正好是能避开多少行的砖。

用哈希表 gaps 统计这些坐标，同时维护最大计数 maxGap。不在任何砖缝上的线会穿过每一行，不可能优于已有砖缝；若所有行都只有一块砖，maxGap 为 0，答案自然是总行数。

解题步骤

1. 创建哈希表 gaps，gaps[p] 表示位置 p 出现过多少条内部缝；初始化 maxGap = 0。
2. 对每一行把 position 重置为 0，只遍历到倒数第二块砖。
3. 累加当前砖宽得到一条内部缝的位置，将 gaps[position] 加一，并更新 maxGap。
4. 所有行处理完后，返回 wall.size() - maxGap。

单块砖宽度虽然不超过 $2^{31}-1$，一行的累计宽度却可能超过这个范围。坐标和哈希键都用 64 位整数，避免不同位置因溢出被误计为同一条缝。

代码实现

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Long, Integer> gaps = new HashMap<>();
        int maxGap = 0;

        for (List<Integer> row : wall) {
            long position = 0;

            // 最后一块后的总宽度是墙外边界，不能作为合法砖缝。
            for (int i = 0; i < row.size() - 1; i++) {
                position += row.get(i);
                int count = gaps.getOrDefault(position, 0) + 1;

                gaps.put(position, count);
                maxGap = Math.max(maxGap, count);
            }
        }

        return wall.size() - maxGap;
    }
}

func leastBricks(wall [][]int) int {
    gaps := make(map[int64]int)
    maxGap := 0
    for _, row := range wall {
        var position int64
        // 最后一块后的总宽度是墙外边界，不能作为合法砖缝。
        for i := 0; i < len(row)-1; i++ {
            position += int64(row[i])
            gaps[position]++
            if gaps[position] > maxGap {
                maxGap = gaps[position]
            }
        }
    }
    return len(wall) - maxGap
}

复杂度分析

• 时间复杂度：$O(T)$，其中 T 是所有砖块的总数；每条内部缝只统计一次。
• 空间复杂度：$O(G)$，其中 G 是不同内部缝位置的数量，且 G <= T。

关键点总结

[!green]

• 最少穿砖数 = 总行数 - 同一坐标上最多的内部砖缝数。
• 前缀宽度给出统一的横坐标，不能按每行第几块砖统计。
• 坐标范围很大，只需用哈希表保存实际出现的内部缝，无需按墙宽开数组。

易错点总结

[!yellow]

• 把最后一块也累加会把墙的右边界算成所有行共享的缝，答案可能错误地变成 0。
• position 必须在每行开始时清零，所有行都以墙的左端为原点。
• 累计坐标不能用 32 位整数；溢出可能让同一行的不同缝碰撞，计数甚至超过行数。
• 每行都只有一块砖时没有合法内部缝，返回行数，而不是 0。

相似题目

题目	难度	关联与区别
560. 和为 K 的子数组	中等	每行砖长前缀和给出内部缝隙坐标，本题按这些坐标计频次，而非查区间和。
347. 前 K 个高频元素	中等	把共同缝隙位置当作值统计频次，频次最高的缝隙使穿过的砖最少。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/99048587

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