Medium

题目描述

给你一个二维整数数组 rectangles ，其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 、高为 hi 。给你一个二维整数数组 points ，其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。

第 i 个矩形的 左下角 在 (0, 0) 处，右上角 在 (li, hi) 处。

请你返回一个整数数组 count ，长度为 points.length ，其中 count[j] 是包含第 j 个点的矩形数目。

如果 0 <= xj <= li 且 0 <= yj <= hi ，那么我们说第 i 个矩形包含第 j 个点。如果点在矩形的 边上 ，这个点也被视为被矩形包含。

示例 1：

输入：rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
输出：[2,1]
解释：
第一个矩形不包含任何点。
第二个矩形只包含一个点 (2, 1) 。
第三个矩形包含点 (2, 1) 和 (1, 4) 。
包含点 (2, 1) 的矩形数目是 2 。
包含点 (1, 4) 的矩形数目是 1 。
所以，我们返回 [2, 1] 。

示例 2：

输入：rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
输出：[1,3]
解释：
第一个矩形只包含点 (1, 1) 。
第二个矩形只包含点 (1, 1) 。
第三个矩形包含点 (1, 3) 和 (1, 1) 。
包含点 (1, 3) 的矩形数目是 1 。
包含点 (1, 1) 的矩形数目是 3 。
所以，我们返回 [1, 3] 。

提示：

  • 1 <= rectangles.length, points.length <= 5 * 10^4
  • rectangles[i].length == points[j].length == 2
  • 1 <= li, xj <= 10^9
  • 1 <= hi, yj <= 100
  • 所有的矩形都是互不相同的。
  • 所有的点都是互不相同的。

解题思路

这道题的关键观察是矩形的高度和点的y坐标都不超过100，这个约束条件非常重要。

解题思路

基本思路： 对于每个查询点，我们需要统计有多少个矩形能够包含它。矩形包含点的条件是：0 <= x <= li 且 0 <= y <= hi。

暴力解法： 对于每个点，遍历所有矩形检查是否包含，时间复杂度O(n*m)，在数据量较大时会超时。

优化思路： 利用高度限制的特点进行优化。由于高度最大只有100，我们可以：

  1. 按高度分组： 将所有矩形按照高度进行分组，对于每个高度h，维护所有高度为h的矩形的长度列表
  2. 排序优化： 对每个高度的长度列表进行排序，这样可以使用二分查找
  3. 高效查询： 对于查询点(x,y)，只需要考虑高度 >= y的所有矩形组。在每个满足条件的高度组中，使用二分查找统计长度 >= x的矩形个数

具体步骤：

  • 遍历每个高度h (从y到100)
  • 在高度为h的矩形长度列表中，二分查找第一个 >= x的位置
  • 累加所有满足条件的矩形数量

这种方法的时间复杂度为O(m * 100 * log n)，其中n是矩形数量，m是点的数量，100是高度的上界。

代码实现

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<vector<int>> groups(101);
        
        // 按高度分组并收集长度
        for (auto& rect : rectangles) {
            groups[rect[1]].push_back(rect[0]);
        }
        
        // 对每个高度组的长度进行排序
        for (int i = 1; i <= 100; i++) {
            sort(groups[i].begin(), groups[i].end());
        }
        
        vector<int> result;
        for (auto& point : points) {
            int x = point[0], y = point[1];
            int count = 0;
            
            // 遍历所有高度 >= y的矩形组
            for (int h = y; h <= 100; h++) {
                // 二分查找长度 >= x的矩形个数
                auto& lengths = groups[h];
                auto it = lower_bound(lengths.begin(), lengths.end(), x);
                count += lengths.end() - it;
            }
            result.push_back(count);
        }
        
        return result;
    }
};

class Solution:
    def countRectangles(self, rectangles: List[List[int]], points: List[List[int]]) -> List[int]:
        from collections import defaultdict
        import bisect
        
        # 按高度分组
        groups = defaultdict(list)
        for length, height in rectangles:
            groups[height].append(length)
        
        # 对每个高度组的长度进行排序
        for height in groups:
            groups[height].sort()
        
        result = []
        for x, y in points:
            count = 0
            # 遍历所有高度 >= y的矩形组
            for h in range(y, 101):
                if h in groups:
                    # 二分查找长度 >= x的矩形个数
                    lengths = groups[h]
                    idx = bisect.bisect_left(lengths, x)
                    count += len(lengths) - idx
            result.append(count)
        
        return result

public class Solution {
    public int[] CountRectangles(int[][] rectangles, int[][] points) {
        var groups = new List<int>[101];
        for (int i = 0; i <= 100; i++) {
            groups[i] = new List<int>();
        }
        
        // 按高度分组
        foreach (var rect in rectangles) {
            groups[rect[1]].Add(rect[0]);
        }
        
        // 对每个高度组的长度进行排序
        for (int i = 1; i <= 100; i++) {
            groups[i].Sort();
        }
        
        var result = new int[points.Length];
        for (int i = 0; i < points.Length; i++) {
            int x = points[i][0], y = points[i][1];
            int count = 0;
            
            // 遍历所有高度 >= y的矩形组
            for (int h = y; h <= 100; h++) {
                var lengths = groups[h];
                // 二分查找长度 >= x的矩形个数
                int idx = BinarySearchLeft(lengths, x);
                count += lengths.Count - idx;
            }
            result[i] = count;
        }
        
        return result;
    }
    
    private int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var countRectangles = function(rectangles, points) {
    const groups = Array.from({length: 101}, () => []);
    
    // 按高度分组
    for (const [length, height] of rectangles) {
        groups[height].push(length);
    }
    
    // 对每个高度组的长度进行排序
    for (let i = 1; i <= 100; i++) {
        groups[i].sort((a, b) => a - b);
    }
    
    const result = [];
    for (const [x, y] of points) {
        let count = 0;
        
        // 遍历所有高度 >= y的矩形组
        for (let h = y; h <= 100; h++) {
            const lengths = groups[h];
            // 二分查找长度 >= x的矩形个数
            const idx = binarySearchLeft(lengths, x);
            count += lengths.length - idx;
        }
        result.push(count);
    }
    
    return result;
};

function binarySearchLeft(arr, target) {
    let left = 0, right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + m × 100 × log n)n为矩形数量，m为点数量。排序O(n log n)，每个点查询O(100 × log n)
空间复杂度O(n)存储按高度分组的矩形长度列表

相关题目