0554. Brick Wall ================ 题目信息 -------- :题号: 0554 :难度: Medium :主题: 砖墙、内部缝隙、垂直线、最少穿砖数 :原题: `LeetCode 0554 `_ :重点: 每行总宽度相同、垂线不能沿墙左右外边界、经过砖缝不算穿砖、返回最少穿过的砖数 题目重述 -------- 一堵墙由若干行砖组成,``wall[i]`` 依次给出第 ``i`` 行每块砖的宽度,所有砖高度相同,并且每行总宽度相同。要从墙顶到墙底画一条竖直线,统计它穿过的砖块数量。 线经过同一行中两块砖之间的缝隙时,不算穿过砖;但不能把线画在整堵墙的最左或最右外边界上。返回能够达到的最少穿砖数量。 自建示例 -------- 所有行存在共同内部缝隙: .. code-block:: text 输入:wall = [[2,1,2],[1,2,2],[3,2]] 输出:0 解释:三行在距左边界 3 的位置都有砖缝,垂线可以完全沿缝穿过。 没有任何内部缝隙: .. code-block:: text 输入:wall = [[5],[5]] 输出:2 解释:每行只有一块砖,任意合法的内部垂线都会穿过两块砖。 统计各行共同出现的内部缝隙 -------------------------- 对每一行累加砖宽得到内部缝隙的位置,忽略该行最后一块砖的总宽度,因为墙的最右外边界不能选。若某个位置在 ``seam`` 行出现,垂线就能在这些行不穿砖;因此穿砖数为总行数减去最多缝隙频次。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int leastBricks(std::vector>& wall) { std::unordered_map frequency; for (const auto& row : wall) { int position = 0; for (int i = 0; i + 1 < static_cast(row.size()); ++i) { position += row[i]; ++frequency[position]; } } int best = 0; for (const auto& [position, count] : frequency) { best = std::max(best, count); } return static_cast(wall.size()) - best; } }; 代码分析 -------- 固定一条合法垂线后,它不穿砖的行恰好是该位置的内部缝隙行;选择频次最高的位置即可最大化免穿砖行数。每块砖的内部边界只统计一次,时间复杂度为 ``O(砖块总数)``,额外空间复杂度为 ``O(缝隙数量)``。