【Leetcode Daily】3531统计被覆盖的建筑

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组代表点集，求其中上下左右都有点的点的个数。

思路分享

• 又是能和灵神思考相近的一次，开心喵。

• 首先考虑暴力解法，那就是对于每一个点，再遍历数组，查看是否该点的横纵坐标都有更大以及更小的值。复杂度已经达到了 O(n^2)。

• 想要降低复杂度，就需要改进判断这个点的上下左右是否有值，那么如果能知道对应的 x，y 坐标上的极值，不就可以了嘛。

• 所以，在遍历所有点前，可以先预处理，记录每个横纵坐标的极值，这样就把二次遍历的过程优化了，时间复杂度下降到了 O(n)。

  https://leetcode.cn/problems/count-covered-buildings/solutions/3663296/pai-xu-er-fen-cha-zhao-pythonjavacgo-by-z2c5d/?envType=daily-question&envId=2025-12-11

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def countCoveredBuildings(self, n: int, buildings: List[List[int]]) -> int:
        vertical_rec_high = [-inf]*(n+1)
        vertical_rec_low = [inf]*(n+1)
        horizon_rec_left = [inf]*(n+1)
        horizon_rec_right = [-inf]*(n+1)
        for x, y in buildings:
            vertical_rec_high[x] = max(vertical_rec_high[x], y)
            vertical_rec_low[x] = min(vertical_rec_low[x], y)
            horizon_rec_left[y] = min(horizon_rec_left[y], x)
            horizon_rec_right[y] = max(horizon_rec_right[y], x)
        ans = 0
        for x, y in buildings:
            if horizon_rec_left[y] < x < horizon_rec_right[y] and vertical_rec_low[x] < y < vertical_rec_high[x]:
                ans += 1
        return ans