3531. 統計被覆蓋的建築

思路

紀錄每一行每一列的極端建築位置（最左、最右、最上、最下），
然後判斷每個建築的位置是否在極端位置之內，如果在，就計入答案當中。

程式碼

class Solution {
public:
    int countCoveredBuildings(int n, vector<vector<int>>& buildings) {
        int res = 0;
        vector<pair<int, int>> row(n + 1); // row[i] 代表 x = i 時的最左跟最右
        vector<pair<int, int>> col(n + 1); // col[i] 代表 y = i 時的最上跟最下
        int m = buildings.size();
        for(auto& vec : buildings) {
            int x = vec[0], y = vec[1];
            if(row[x].first == 0 && row[x].second == 0) { // 初始數值
                row[x].first = y;
                row[x].second = y;
            }
            row[x].first = min(row[x].first, y);
            row[x].second = max(row[x].second, y);

            if(col[y].first == 0 && col[y].second == 0) { // 初始數值
                col[y].first = x;
                col[y].first = x;
            }
            col[y].first = min(col[y].first, x);
            col[y].second = max(col[y].second, x);
        }
        for(auto& vec : buildings) {
            int x = vec[0], y = vec[1];
            if(row[x].first < y && y < row[x].second && 
               col[y].first < x && x < col[y].second) {
                ++res;
               }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n + m)$, m是 building 的長度。
• 空間複雜度：$O(n)$