題目描述:wall 是一面磚牆,wall[i] 是第 i 行磚的寬度列表(每行總寬相同)。畫一條從上到下的垂直線,使穿過的磚塊數量最少(線不可沿兩端邊界走)。回傳最少穿磚數。
解題思路:
核心洞見:垂直線穿過的磚數 = 總行數 - 垂直線經過的磚縫數。因此,最少穿磚數 = 總行數 - 最多磚縫重合數。
演算法:
unordered_map<int,int> gapCount 統計每個橫向位置(距左邊界的累積寬度)出現磚縫的次數。gapCount 中最大值 maxGaps。wall.size() - maxGaps。若所有位置都沒有磚縫(例如每行只有一塊磚),則 maxGaps = 0,答案 = 總行數(穿過每一行)。
時間複雜度:O(n) — 其中 n 為所有磚的總數(每塊磚僅處理一次以計算前綴和)。
空間複雜度:O(W) — 其中 W 為牆的總寬度(哈希表最多儲存 W-1 個不同的磚縫位置)。
1. Initialize gapCount = empty hashmap, maxGaps = 0
2. For each row in wall:
a. x = 0
b. For each brick width (except last) in row:
x += width
gapCount[x]++
maxGaps = max(maxGaps, gapCount[x])
3. Return wall.size() - maxGaps排序計數法:對每行計算所有磚縫位置,收集到一個全局陣列後排序,計數最多重複的值——時間 O(n log n),空間 O(n),比哈希表慢。
暴力掃描 O(W × R):對每個可能的垂直位置(1 到 W-1),逐行判斷是否在磚縫上——W 可達 10⁷,行數 R 可達 10⁴,總計 O(W×R) 會超時。
排序行後的差分陣列:若牆寬 W 固定且較小,可用長度 W 的陣列替代哈希表,避免哈希碰撞,常數因子更小。