554. Brick Wall

Medium

Description

給定一面磚牆（2D 陣列表示每行磚塊的寬度），畫一條從頂到底的垂直線，使得穿過的磚塊數最少。如果線恰好在磚塊邊界上，不算穿過。回傳穿過的最少磚塊數。

Example:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]] Output: 2

Intuition#

核心思路：「穿過最少磚塊」等價於「經過最多邊界」。統計每個位置有多少邊界，取最大值，答案 = 行數 - 最多邊界數。

對每一行計算前綴和（不含最後一塊），前綴和代表邊界位置
用 HashMap 統計每個邊界位置出現幾次
出現最多次的邊界位置就是最佳畫線位置

Approaches#

1: Brute Force（每個位置都試）#

概念: 對每個可能的 x 位置，檢查每行是否有邊界
時間複雜度: O(n * W) - n 為行數，W 為牆寬
空間複雜度: O(n * W) - 儲存所有邊界

class Solution {
    fun leastBricks(wall: List<List<Int>>): Int {
        val width = wall[0].sum()
        val borders = Array(wall.size) { HashSet<Int>() }
        for (i in wall.indices) {
            var sum = 0
            for (j in 0 until wall[i].size - 1) {
                sum += wall[i][j]
                borders[i].add(sum)
            }
        }
        var maxBorders = 0
        for (x in 1 until width) {
            var count = 0
            for (i in wall.indices) {
                if (x in borders[i]) count++
            }
            maxBorders = maxOf(maxBorders, count)
        }
        return wall.size - maxBorders
    }
}

⭐2: HashMap 統計邊界頻率#

概念: 對每行計算邊界位置（前綴和），用 HashMap 統計每個位置出現次數，取最大值
時間複雜度: O(n * m) - n 為行數，m 為每行平均磚塊數
空間複雜度: O(n * m) - HashMap

class Solution {
    fun leastBricks(wall: List<List<Int>>): Int {
        val borderCount = HashMap<Int, Int>()
        for (row in wall) {
            var sum = 0
            for (i in 0 until row.size - 1) {
                sum += row[i]
                borderCount[sum] = (borderCount[sum] ?: 0) + 1
            }
        }
        val maxBorders = borderCount.values.maxOrNull() ?: 0
        return wall.size - maxBorders
    }
}

🔑 Takeaways#

Pattern: 轉換問題——「最小化穿過」轉為「最大化對齊邊界」
關鍵技巧: 前綴和求邊界位置 + HashMap 計頻率；注意不要包含牆的最右邊界（因為所有行都在那裡結束）