LeetCode 3531 – Count Covered Buildings 题解
给定一个正整数 n 表示一座 n x n 的城市网格,以及一个数组 buildings,其中 buildings[i] = [x, y] 表示在坐标 (x, y) 上有一栋建筑,且所有坐标互不相同。leetcode
如果某栋建筑在四个方向上都至少有一栋其他建筑(左、右、上、下),则称这栋建筑是「被覆盖的」。形式化地说,对建筑 (x, y):
- 同一行 x 上,存在列坐标小于 y 的建筑(左边);
- 同一行 x 上,存在列坐标大于 y 的建筑(右边);
- 同一列 y 上,存在行坐标小于 x 的建筑(上边或下边,取决于坐标系约定);
- 同一列 y 上,存在行坐标大于 x 的建筑(与上一个相反方向)。
问:共有多少栋建筑是被覆盖的?leetcode
朴素直觉:从每栋建筑向四个方向扫
一开始很自然的想法是:
- 遍历每一个建筑 (x, y);
- 向左、向右、向上、向下在整个 n x n 网格上「扫」一条线,看看能不能找到其他建筑;
- 如果四个方向都找到了,就把答案加一。
这个思路在正确性上其实没问题,因为定义就是这样:四个方向上只要能找到至少一栋建筑就行。问题在于效率。
约束中 n 最多可以到 10^5,buildings.length 也可以到 10^5。leetcode
如果你真在网格上按行、按列一路扫到边界,最坏情况下:
- 对每栋建筑,向某个方向扫描要走 O(n);
- 有 4 个方向,因此大约 O(4n);
- 一共有 m = buildings.length 栋建筑,总复杂度约是 O(m · n)。
在 n 和 m 都到 10^5 量级时,O(m · n) 接近 10^10 级别,完全超出可接受范围,这就是面试官会否掉这种方案的原因。
换个视角:真正「需要」的信息是什么?
关键问题是:判断 (x, y) 是否被覆盖,真的需要在网格上一个格子一个格子地扫吗?
观察定义可以发现,只关心「有没有建筑」,而且只在同一行和同一列上:youtube algo
对水平方向:
- 是否存在 (x, y_left),使得 y_left < y?
- 是否存在 (x, y_right),使得 y_right > y?
对垂直方向:
- 是否存在 (x_up, y),使得 x_up < x?
- 是否存在 (x_down, y),使得 x_down > x?
换句话说,只要知道:
- 在行 x 里,所有建筑的列坐标的最小值和最大值;
- 在列 y 里,所有建筑的行坐标的最小值和最大值;
就可以知道 (x, y) 是否被「夹在中间」。algo youtube
核心思路:按行按列维护最小/最大坐标
下面是一个非常高效、又很「面试友好」的做法:
第一步:按行、按列收集坐标
对每一栋建筑 (x, y):
- 在「按行」的结构里,把该行的 y 放进去;
- 在「按列」的结构里,把该列的 x 放进去。
可以用两种方式来实现:
- 使用 map + 排序,维护每一行/每一列的一个排序后的坐标列表;algo
- 或者更直接地,为每行维护 minY[x] 和 maxY[x],为每列维护 minX[y] 和 maxX[y]。linkedin
只维护最小/最大更轻量,这里用这种版本来说明思路。
初始化:
- minY[x] 初始为一个极大值,maxY[x] 初始为一个极小值;
- minX[y] 和 maxX[y] 同理。
遍历所有建筑 (x, y) 时:
- minY[x] = min(minY[x], y);
- maxY[x] = max(maxY[x], y);
- minX[y] = min(minX[y], x);
- maxX[y] = max(maxX[y], x)。youtube linkedin
这一趟遍历是 O(m)。
直觉上:
- minY[x] 就是这一行最左边的建筑;
- maxY[x] 就是这一行最右边的建筑;
- minX[y] 是这一列最上/下边(取决于坐标系)的建筑;
- maxX[y] 是这一列最下/上边的建筑。
第二步:判断每栋建筑是否「被夹住」
再遍历一遍 buildings,对于每个 (x, y),检查:youtube algo
- 左边是否有建筑:minY[x] < y;
- 右边是否有建筑:maxY[x] > y;
- 上边是否有建筑:minX[y] < x;
- 下边是否有建筑:maxX[y] > x。
如果四个条件全部满足,就说明 (x, y) 在行上被左右夹住、在列上被上下夹住,是一个被覆盖的建筑,答案加一。algo youtube
从更直观的角度看:
- minY[x] < y < maxY[x] ⇒ 同一行里它不是最左也不是最右,两侧都有建筑。
- minX[y] < x < maxX[y] ⇒ 同一列里它不是最上/最下,两侧都有建筑。
复杂度分析
- 第一次遍历:更新每行/每列的最小值和最大值,时间 O(m)。algo
- 第二次遍历:对每栋建筑做 O(1) 判断,时间也是 O(m)。algo
- 总时间复杂度O(m),空间复杂度是 O(n) 级别用来存储这些最值信息,非常适合在面试中展示。
细节补充:一些边界与剪枝
还可以做一个小优化:
- 要在一行里有「左和右」两个方向,至少得有 3 栋建筑;
- 要在一列里有「上和下」两个方向,同样至少得有 3 栋建筑。algo
所以在第二次遍历建筑时,可以:
- 统计每行 cntRow[x] 和每列 cntCol[y] 的建筑数量;
- 如果 cntRow[x] < 3 或 cntCol[y] < 3,这栋建筑肯定不可能被覆盖,可以直接跳过判断。algo
这个剪枝在数据比较分散时很划算,也能给面试官展示你对条件的深入理解。
参考代码示例(伪代码风格)
下面是接近实际代码的伪代码结构,和上面描述一致:
function countCoveredBuildings(n, buildings): // 假设行和列都是 1..n INF = +∞ // 用数组或哈希表都可以 minY = array[1..n] filled with INF maxY = array[1..n] filled with -INF minX = array[1..n] filled with INF maxX = array[1..n] filled with -INF cntRow = array[1..n] filled with 0 cntCol = array[1..n] filled with 0 // 第一次遍历:更新最值和计数 for (x, y) in buildings: minY[x] = min(minY[x], y) maxY[x] = max(maxY[x], y) minX[y] = min(minX[y], x) maxX[y] = max(maxX[y], x) cntRow[x] += 1 cntCol[y] += 1 ans = 0 // 第二次遍历:判断是否覆盖 for (x, y) in buildings: // 剪枝:行或列少于 3 栋,直接不可能 if cntRow[x] < 3 or cntCol[y] < 3: continue if minY[x] < y and y < maxY[x] and minX[y] < x and x < maxX[y]: ans += 1 return ans这一解法的核心在于:把「是否有建筑」抽象成「是否在最小值和最大值之间」,避免对网格做任何无谓的扫描。linkedin youtube
