給定一面磚牆（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
TIP
核心思路：「穿過最少磚塊」等價於「經過最多邊界」。統計每個位置有多少邊界，取最大值，答案 = 行數 - 最多邊界數。
- 對每一行計算前綴和（不含最後一塊），前綴和代表邊界位置
- 用 HashMap 統計每個邊界位置出現幾次
- 出現最多次的邊界位置就是最佳畫線位置
Approaches
1. Brute Force (try every position) — O(n * W) / O(n * W)
- Idea: 對每個可能的 x 位置，檢查每行是否有邊界
- Time:
O(n * W)- n 為行數，W 為牆寬 - Space:
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 Boundary Frequency — O(n * m) / O(n * m)
- Idea: 對每行計算邊界位置（前綴和），用 HashMap 統計每個位置出現次數，取最大值
- Time:
O(n * m)- n 為行數，m 為每行平均磚塊數 - Space:
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: 轉換問題——「最小化穿過」轉為「最大化對齊邊界」
- Key trick: 前綴和求邊界位置 + HashMap 計頻率；注意不要包含牆的最右邊界（因為所有行都在那裡結束）