Medium

题目描述

你的面前有一堵矩形的砖墙，由 n 行砖块组成。第 i 行有若干块砖，每块砖的高度相同（即一个单位），但它们的宽度可以不同。每一行的总宽度都相同。

从顶部到底部画一条垂直线，穿过最少的砖块。如果你的线穿过砖块的边缘，那么该砖块不被认为是穿过的。你不能沿着墙的两个垂直边缘中的一个画线，在这种情况下，线显然不会穿过任何砖块。

给定包含墙信息的二维数组 wall，返回画这样一条垂直线后穿过的砖块的最小数量。

示例 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. 观察规律：如果一条垂直线经过了 k 个砖块的缝隙，那么它就只需要穿过 n-k 个砖块（其中 n 是墙的行数）
  2. 问题转化：原问题等价于找到经过最多缝隙的垂直线位置

算法步骤

  1. 记录缝隙位置：遍历每一行砖块，计算每个砖块的累计宽度（除了最后一块砖，因为不能画在墙的边缘）
  2. 统计频次：使用哈希表记录每个位置出现的缝隙次数
  3. 找最大值：找到出现次数最多的缝隙位置
  4. 计算结果：用总行数减去最大缝隙次数

复杂度分析

  • 时间复杂度：O(sum(wall[i].length))，需要遍历所有砖块
  • 空间复杂度：O(总缝隙数)，哈希表存储缝隙位置

这种方法避免了枚举所有可能的垂直线位置，而是直接统计有意义的缝隙位置，效率很高。

代码实现

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> edgeCount;
        
        for (const auto& row : wall) {
            int position = 0;
            // 遍历除了最后一块砖之外的所有砖
            for (int i = 0; i < row.size() - 1; i++) {
                position += row[i];
                edgeCount[position]++;
            }
        }
        
        int maxEdges = 0;
        for (const auto& pair : edgeCount) {
            maxEdges = max(maxEdges, pair.second);
        }
        
        return wall.size() - maxEdges;
    }
};

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        edge_count = {}
        
        for row in wall:
            position = 0
            # 遍历除了最后一块砖之外的所有砖
            for i in range(len(row) - 1):
                position += row[i]
                edge_count[position] = edge_count.get(position, 0) + 1
        
        max_edges = max(edge_count.values()) if edge_count else 0
        return len(wall) - max_edges

public class Solution {
    public int LeastBricks(IList<IList<int>> wall) {
        Dictionary<int, int> edgeCount = new Dictionary<int, int>();
        
        foreach (var row in wall) {
            int position = 0;
            // 遍历除了最后一块砖之外的所有砖
            for (int i = 0; i < row.Count - 1; i++) {
                position += row[i];
                if (edgeCount.ContainsKey(position)) {
                    edgeCount[position]++;
                } else {
                    edgeCount[position] = 1;
                }
            }
        }
        
        int maxEdges = 0;
        foreach (var pair in edgeCount) {
            maxEdges = Math.Max(maxEdges, pair.Value);
        }
        
        return wall.Count - maxEdges;
    }
}

/**
 * @param {number[][]} wall
 * @return {number}
 */
var leastBricks = function(wall) {
    const edgeCount = new Map();
    
    for (const row of wall) {
        let position = 0;
        // 遍历除了最后一块砖之外的所有砖
        for (let i = 0; i < row.length - 1; i++) {
            position += row[i];
            edgeCount.set(position, (edgeCount.get(position) || 0) + 1);
        }
    }
    
    let maxEdges = 0;
    for (const count of edgeCount.values()) {
        maxEdges = Math.max(maxEdges, count);
    }
    
    return wall.length - maxEdges;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(∑wall[i].length)需要遍历所有砖块来计算缝隙位置
空间复杂度O(缝隙总数)哈希表存储所有可能的缝隙位置及其出现次数

相关题目