题目

给你一个正整数 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 中所有坐标均唯一。

解题思路

核心解题思路：利用极值（Min/Max）

一个建筑 $(x, y)$ 想要被“覆盖”，它必须满足以下两个条件：

水平方向（行）： 它不能是该行最左边的建筑，也不能是该行最右边的建筑。换句话说，它的列坐标 $y$ 必须严格位于该行所有建筑的最小列坐标和最大列坐标之间。
垂直方向（列）： 它不能是该列最上边的建筑，也不能是该列最下边的建筑。换句话说，它的行坐标 $x$ 必须严格位于该列所有建筑的最小行坐标和最大行坐标之间。

详细算法步骤

数据结构准备：我们需要四个数组（或哈希表）来存储每一行和每一列的边界信息：初始化：Min 数组初始化为无穷大，Max 数组初始化为无穷小（或 -1）。
- row_min_y[x]：记录第 $x$ 行中，建筑的最小 $y$ 坐标（最左）。
- row_max_y[x]：记录第 $x$ 行中，建筑的最大 $y$ 坐标（最右）。
- col_min_x[y]：记录第 $y$ 列中，建筑的最小 $x$ 坐标（最上）。
- col_max_x[y]：记录第 $y$ 列中，建筑的最大 $x$ 坐标（最下）。
第一次遍历（预处理）：遍历 buildings 数组中的每一个坐标 [x, y]，更新上述四个数组：
- 更新第 $x$ 行的最小/最大 $y$。
- 更新第 $y$ 列的最小/最大 $x$。
第二次遍历（统计答案）：再次遍历 buildings 数组中的每一个坐标 [x, y]，检查它是否满足被覆盖的条件：
- 条件 1：row_min_y[x] < y < row_max_y[x] （左右都有人）
- 条件 2：col_min_x[y] < x < col_max_x[y] （上下都有人）
- 如果同时满足，计数器 count 加 1。
返回结果：返回 count。

具体代码

func countCoveredBuildings(n int, buildings [][]int) int {
    // 初始化用于存储每行和每列边界值的切片
    // 坐标是 1 到 n，所以长度设为 n + 1
    // 空间复杂度: O(N)
    minRow := make([]int, n+1)
    maxRow := make([]int, n+1)
    minCol := make([]int, n+1)
    maxCol := make([]int, n+1)

    // 初始化极值
    // min 初始化为一个比最大坐标 n 大的数 (比如 n + 1)
    // max 初始化为一个比最小坐标 1 小的数 (比如 0)
    for i := 0; i <= n; i++ {
        minRow[i] = n + 1
        maxRow[i] = 0
        minCol[i] = n + 1
        maxCol[i] = 0
    }

    // 第一遍遍历：构建每一行和每一列的边界信息
    // 时间复杂度: O(K)
    for _, b := range buildings {
        x, y := b[0], b[1]

        // 更新第 x 行的最小和最大 y
        if y < minRow[x] {
            minRow[x] = y
        }
        if y > maxRow[x] {
            maxRow[x] = y
        }

        // 更新第 y 列的最小和最大 x
        if x < minCol[y] {
            minCol[y] = x
        }
        if x > maxCol[y] {
            maxCol[y] = x
        }
    }

    count := 0

    // 第二遍遍历：统计符合条件的建筑
    // 时间复杂度: O(K)
    for _, b := range buildings {
        x, y := b[0], b[1]

        // 检查水平方向：是否严格位于该行最左和最右建筑之间
        rowCovered := y > minRow[x] && y < maxRow[x]

        // 检查垂直方向：是否严格位于该列最上和最下建筑之间
        colCovered := x > minCol[y] && x < maxCol[y]

        if rowCovered && colCovered {
            count++
        }
    }

    return count
}

3531. 统计被覆盖的建筑

beautifulremi

题目

解题思路

核心解题思路：利用极值（Min/Max）

详细算法步骤

具体代码