LeetCode 解題筆記：554. Brick Wall

作者：王一哲
日期：2026年8月21日


LeetCode 題目連結：554. Brick Wall

解題想法

中等難度題。題目給一個 $n$ 列的二維陣列 $wall$，每一列代表這列之中由左到右每個磚塊的寬度，題目假設要從地面往上畫一條鉛直線，這條線穿過的磚塊數量最少為幾塊。這題要反過來寫，先找出磚塊之間的接縫位置，計算接縫位置的數量，答案就是 $n$ 減去接縫數量的最小值。由於每列的總寬度極大，但是接縫數量不會太大，很適合用字典計數。用 C++ 解題要注意，接縫的位置會超出 int 的上限，要用 long 才不會溢位。

Python 程式碼

使用預設的 dict。Runtime: 3 ms, beats 93.16%. Memory: 22.97 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = dict()  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                if pos not in psum:
                    psum[pos] = 1
                else:
                    psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

使用 collections.defaultdict。Runtime: 7 ms, beats 70.30%. Memory: 22.92 MB, beats 22.08%.

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)  # n 列磚塊
        psum = defaultdict(int)  # 磚塊接縫的位置及次數
        for w in wall:
            pos = 0
            for x in w[:-1]:  # 不含整列的最右側
                pos += x
                psum[pos] += 1
        # 答案為 n - 出現最多次的接縫位置
        return n if not psum.values() else n - max(psum.values())

C++ 程式碼

Runtime: 11 ms, beats 35.11%. Memory: 28.64 MB, beats 5.93%.

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        int n = (int)wall.size();
        unordered_map<long, int> psum;
        for(auto w : wall) {
            long pos = 0;
            int m = (int)w.size();
            for(int i = 0; i < m-1; i++) {
                pos += w[i];
                psum[pos]++;
            }
        }
        if (psum.empty()) {
            return n;
        } else {
            int imax = 0;
            for(auto it : psum) {
                imax = max(imax, it.second);
            }
            return n - imax;
        }
    }
};

Runtime: 8 ms, beats 53.74%. Memory: 28.43 MB, beats 8.66%.

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        int n = (int)wall.size();
        unordered_map<long, int> psum;
        for(auto w : wall) {
            long pos = 0;
            int m = (int)w.size();
            for(int i = 0; i < m-1; i++) {
                pos += w[i];
                psum[pos]++;
            }
        }
        if (psum.empty()) {
            return n;
        } else {
            auto max_it = *max_element(psum.begin(), psum.end(),
                [](const auto& a, const auto& b) {
                    return a.second < b.second;
                });
            return n - max_it.second;
        }
    }
};