3531.统计被覆盖的建筑：最大最小值

【LetMeFly】3531.统计被覆盖的建筑：最大最小值

力扣题目链接：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] 被覆盖，因为它在每个方向上都至少存在一个建筑：

  <ul>
  	<li>上方 (<code>[1,2]</code>)</li>
  	<li>下方 (<code>[3,2]</code>)</li>
  	<li>左方 (<code>[2,1]</code>)</li>
  	<li>右方 (<code>[2,3]</code>)</li>
  </ul>
  </li>
  <li>因此，被覆盖的建筑数量是 1。</li>
  

示例 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] 被覆盖，因为它在每个方向上至少存在一个建筑：

  <ul>
  	<li>上方 (<code>[1,3]</code>)</li>
  	<li>下方 (<code>[5,3]</code>)</li>
  	<li>左方 (<code>[3,2]</code>)</li>
  	<li>右方 (<code>[3,5]</code>)</li>
  </ul>
  </li>
  <li>因此，被覆盖的建筑数量是 1。</li>
  

 

提示：

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

解题方法：最大最小值

遍历一遍所有点可以得到如下信息：

1. 使用两个数组xm和xM，分别记录所有横坐标为x的点中纵坐标的最小值和最大值；
2. 使用两个数组ym和yM，分别记录所有纵坐标为y的点中横坐标的最小值和最大值。

接着遍历一遍所有点（假设横纵坐标分别是x和y）：

如果$ym[y]\lt x\lt yM[y]$并且$xm[x]\lt y\lt xM[x]$则说明这个点上下左右都有点，答案加一。

• 时间复杂度$O(n+len(buildings))$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2025-12-11 13:23:40
 */
class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        n++;
        vector<int> xm(n, n), xM(n), ym(n, n), yM(n);
        for (vector<int>& building : buildings) {
            int x = building[0], y = building[1];
            xm[x] = min(xm[x], y);
            xM[x] = max(xM[x], y);
            ym[y] = min(ym[y], x);
            yM[y] = max(yM[y], x);
        }
        int ans = 0;
        for (vector<int>& building : buildings) {
            int x = building[0], y = building[1];
            ans += xm[x] < y && y < xM[x] && ym[y] < x && x < yM[y];
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2025-12-11 13:27:34
'''
from typing import List

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        n += 1
        xm = [n] * n
        xM = [0] * n
        ym = [n] * n
        yM = [0] * n
        for x, y in buildings:
            xm[x] = min(xm[x], y)
            xM[x] = max(xM[x], y)
            ym[y] = min(ym[y], x)
            yM[y] = max(yM[y], x)
        ans = 0
        for x, y in buildings:
            ans += xm[x] < y < xM[x] and ym[y] < x < yM[y]
        return ans

Java

/*
 * @LastEditTime: 2025-12-11 13:40:24
 */
import java.util.Arrays;

class Solution {
    public int countCoveredBuildings(int n, int[][] buildings) {
        n++;
        int[] xm = new int[n];
        int[] xM = new int[n];
        int[] ym = new int[n];
        int[] yM = new int[n];
        Arrays.fill(xm, n);
        Arrays.fill(ym, n);

        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            xm[x] = Math.min(xm[x], y);
            xM[x] = Math.max(xM[x], y);
            ym[y] = Math.min(ym[y], x);
            yM[y] = Math.max(yM[y], x);
        }

        int ans = 0;
        for (int[] building : buildings) {
            int x = building[0], y = building[1];
            if (xm[x] < y && y < xM[x] && ym[y] < x && x < yM[y]) {
                ans++;
            }
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2025-12-11 13:35:38
 */
package main

func countCoveredBuildings(n int, buildings [][]int) (ans int) {
    n++
    xm := make([]int, n)
    xM := make([]int, n)
    ym := make([]int, n)
    yM := make([]int, n)
    for i := range xm {
        xm[i] = n
        ym[i] = n
    }

    for _, building := range buildings {
        x, y := building[0], building[1]
        xm[x] = min(xm[x], y)
        xM[x] = max(xM[x], y)
        ym[y] = min(ym[y], x)
        yM[y] = max(yM[y], x)
    }

    for _, building := range buildings {
        x, y := building[0], building[1]
        if xm[x] < y && y < xM[x] && ym[y] < x && x < yM[y] {
            ans++
        }
    }
    return
}

Rust

/*
 * @LastEditTime: 2025-12-11 13:48:09
 */
impl Solution {
    pub fn count_covered_buildings(mut n: i32, buildings: Vec<Vec<i32>>) -> i32 {
        n += 1;
        let mut xm: Vec<i32> = vec![n; n as usize];
        let mut xM: Vec<i32> = vec![0; n as usize];
        let mut ym: Vec<i32> = vec![n; n as usize];
        let mut yM: Vec<i32> = vec![0; n as usize];

        for building in buildings.iter() {
            let x: i32 = building[0];
            let y: i32 = building[1];
            xm[x as usize] = xm[x as usize].min(y);
            xM[x as usize] = xM[x as usize].max(y);
            ym[y as usize] = ym[y as usize].min(x);
            yM[y as usize] = yM[y as usize].max(x);
        }

        let mut ans: i32 = 0;
        for building in buildings.iter() {
            let x: i32 = building[0];
            let y: i32 = building[1];
            if xm[x as usize] < y && y < xM[x as usize] && ym[y as usize] < x && x < yM[y as usize] {
                ans += 1;
            }
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源