3531. 统计被覆盖的建筑物

Source: Dev.to

Problem Description

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

如果一个建筑在 四个方向（左、右、上、下）中各至少存在另一座建筑，则该建筑被称为 被覆盖。
返回被覆盖的建筑数量。

Examples

Example 1

Input: n = 3, buildings = [[1,2],[2,2],[3,2],[2,1],[2,3]]
Output: 1

Explanation:
只有建筑 [2,2] 被覆盖，因为它上方有 [1,2]，下方有 [3,2]，左侧有 [2,1]，右侧有 [2,3]。

Example 2

Input: n = 3, buildings = [[1,1],[1,2],[2,1],[2,2]]
Output: 0

Explanation:
没有建筑在四个方向上都有邻居。

Example 3

Input: n = 5, buildings = [[1,3],[3,2],[3,3],[3,5],[5,3]]
Output: 1

Explanation:
只有建筑 [3,3] 被覆盖（上方 [1,3]，下方 [5,3]，左侧 [3,2]，右侧 [3,5]）。

Constraints

• 2 ≤ n ≤ 10⁵
• 1 ≤ buildings.length ≤ 10⁵
• buildings[i] = [x, y]
• 1 ≤ x, y ≤ n
• 所有建筑的坐标均唯一。

Hint

将具有相同 x 或 y 值的建筑归为一组，并对每组进行排序。
在每个已排序的列表中，不是第一个或最后一个位置的建筑在该方向上都有邻居。

Solution Overview

我们需要判断每座建筑是否在四个方向上各至少有一座邻居。
直接的 O(m²) 检查（其中 m 为建筑数量）太慢。
因此，我们：

1. 按列 (x) 和按行 (y) 对建筑进行分组。
2. 对每组进行排序。
3. 对每座建筑，利用它在排序后列和行中的位置来判断是否有上/下和左/右邻居。
4. 统计 在四个方向上都有邻居的建筑。

Algorithm Details

按坐标分组

• xMap[x] → 该列 x 中所有建筑的 y 值列表。
• yMap[y] → 该行 y 中所有建筑的 x 值列表。

判断垂直覆盖（上 / 下）

对 xMap 中的每一列 x：

1. 对该列的 y 列表进行排序。
2. 对列中的每座建筑 (x, y)：
   • 若它不是最小的 y，则它上方有建筑。
   • 若它不是最大的 y，则它下方有建筑。

判断水平覆盖（左 / 右）

对 yMap 中的每一行 y：

1. 对该行的 x 列表进行排序。
2. 对行中的每座建筑 (x, y)：
   • 若它不是最小的 x，则它左侧有建筑。
   • 若它不是最大的 x，则它右侧有建筑。

统计被覆盖的建筑

为每座建筑维护一个状态映射，包含四个布尔标记（above、below、left、right）。
在处理完两个维度后，若四个标记全部为真，则计入结果。

Complexity Analysis

• 时间复杂度： O(m log m)，其中 m = buildings.length。

  • 分组：O(m)
  • 对所有组进行排序（总计）：O(m log m)
  • 扫描组并设置标记：O(m)

• 空间复杂度： O(m)，用于存放分组映射和状态信息。

Reference Implementation (PHP)

// list of y, y => list of x
$xMap = [];
$yMap = [];

// Store each building's index for quick status updates
$indexMap = []; // "x,y" => idx
foreach ($buildings as $idx => $b) {
    [$x, $y] = $b;
    $xMap[$x][] = $y;
    $yMap[$y][] = $x;
    $indexMap["$x,$y"] = $idx;
}

// Status flags: each entry is ['above'=>false,'below'=>false,'left'=>false,'right'=>false]
$status = array_fill(0, $m, [
    'above' => false,
    'below' => false,
    'left'  => false,
    'right' => false,
]);

// Vertical check (above / below)
foreach ($xMap as $x => $ys) {
    sort($ys, SORT_NUMERIC);
    $cnt = count($ys);
    foreach ($ys as $pos => $y) {
        $idx = $indexMap["$x,$y"];
        if ($pos > 0) {
            $status[$idx]['above'] = true;   // there is a smaller y (above)
        }
        if ($pos < $cnt - 1) {
            $status[$idx]['below'] = true;   // there is a larger y (below)
        }
    }
}

// Horizontal check (left / right)
foreach ($yMap as $y => $xs) {
    sort($xs, SORT_NUMERIC);
    $cnt = count($xs);
    foreach ($xs as $pos => $x) {
        $idx = $indexMap["$x,$y"];
        if ($pos > 0) {
            $status[$idx]['left'] = true;    // smaller x exists
        }
        if ($pos < $cnt - 1) {
            $status[$idx]['right'] = true;   // larger x exists
        }
    }
}

// Count covered buildings
$covered = 0;
foreach ($status as $flags) {
    if ($flags['above'] && $flags['below'] && $flags['left'] && $flags['right']) {
        $covered++;
    }
}
return $covered;