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