M3531.统计被覆盖的建筑

implementation, https://leetcode.cn/problems/count-covered-buildings/

给你一个正整数 n，表示一个 n x n 的城市，同时给定一个二维数组 buildings，其中 buildings[i] = [x, y]表示位于坐标 [x, y] 的一个唯一建筑。

如果一个建筑在四个方向（左、右、上、下）中每个方向上都至少存在一个建筑，则称该建筑 被覆盖 。

返回 被覆盖 的建筑数量。

示例 1：

输入: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]

输出: 1

解释:

只有建筑[2,2]被覆盖，因为它在每个方向上都至少存在一个建筑：
- 上方 ([1,2])
- 下方 ([3,2])
- 左方 ([2,1])
- 右方 ([2,3])
因此，被覆盖的建筑数量是 1。

示例 2：

输入: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]

输出: 0

解释:

没有任何一个建筑在每个方向上都有至少一个建筑。

示例 3：

输入: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]

输出: 1

解释:

只有建筑[3,3]被覆盖，因为它在每个方向上至少存在一个建筑：
- 上方 ([1,3])
- 下方 ([5,3])
- 左方 ([3,2])
- 右方 ([3,5])
因此，被覆盖的建筑数量是 1。

提示：

2 <= n <= 10^5
1 <= buildings.length <= 10^5
buildings[i] = [x, y]
1 <= x, y <= n
buildings 中所有坐标均唯一。

思路是：

先遍历一次所有建筑，统计每一行（相同 x）的最小列号和最大列号，以及每一列（相同 y）的最小行号和最大行号。
再遍历一次，每个建筑 (x,y) 同时满足：
- 在它同一行上，存在列号更小的建筑（即 y>row_min[x]）且存在列号更大的建筑（即 y<row_max[x]）；
- 在它同一列上，存在行号更小的建筑（即 x>col_min[y]）且存在行号更大的建筑（即 x<col_max[y]）。
满足以上四个条件的建筑即为“被覆盖”建筑。

python

from typing import List
import collections

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        # row_min[x], row_max[x] 分别记录行 x 上的最小列号和最大列号
        row_min = collections.defaultdict(lambda: float('inf'))
        row_max = collections.defaultdict(lambda: float('-inf'))
        # col_min[y], col_max[y] 分别记录列 y 上的最小行号和最大行号
        col_min = collections.defaultdict(lambda: float('inf'))
        col_max = collections.defaultdict(lambda: float('-inf'))
        
        # 第一次遍历：填充行/列的极值
        for x, y in buildings:
            if y < row_min[x]:
                row_min[x] = y
            if y > row_max[x]:
                row_max[x] = y
            if x < col_min[y]:
                col_min[y] = x
            if x > col_max[y]:
                col_max[y] = x
        
        # 第二次遍历：判断每个建筑是否在四个方向上都有其他建筑
        covered = 0
        for x, y in buildings:
            # 左：y > row_min[x]
            # 右：y < row_max[x]
            # 上：x > col_min[y]
            # 下：x < col_max[y]
            if (y > row_min[x] and y < row_max[x] and
                x > col_min[y] and x < col_max[y]):
                covered += 1
        
        return covered

复杂度分析：

时间复杂度：O(m)，其中 m 为 buildings.length，第一次和第二次遍历都是线性的。
空间复杂度：O(m)，用于存储行/列的极值映射。

M3531.统计被覆盖的建筑 ​

M3531.统计被覆盖的建筑