Leetcode-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 * 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，根据同一个间隙编号只会在单行内被统计一次，用总行数减去出现次数，即得到「最少穿过的砖块数」。

class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        // 1. 哈希表统计所有的砖块间隙
        int n = wall.size();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < n;i++){
            int sum = 0;                                    // 每次统计用来清0
            for(int brick_width:wall.get(i)){
                sum += brick_width;                         // 统计每行的砖块间隔位置
                map.put(sum, map.getOrDefault(sum, 0) + 1); // 间隔出现的次数放入哈希表中
            }
            map.remove(sum);                                // 不能从两边穿过，需要 remove 掉最后一个
        }

        // 2. 比较最小通过的砖块数量
        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)

打赏