Hard

题目描述

给你一个大小为 n x 2 的二维数组 points，表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi]。

我们定义右方向为正 x 轴（x 坐标增加），左方向为负 x 轴（x 坐标减少）。类似地，我们定义上方向为正 y 轴（y 坐标增加），下方向为负 y 轴（y 坐标减少）。

你需要在这些点上放置 n 个人，包括 Alice 和 Bob，使得每个点恰好有一个人。Alice 想要和 Bob 单独在一起，所以 Alice 会建造一个矩形围栏，以 Alice 的位置作为围栏的左上角，Bob 的位置作为围栏的右下角（注意围栏可能不包围任何区域，即它可以是一条线）。如果除了 Alice 和 Bob 之外的任何人在围栏内部或围栏上，Alice 就会不开心。

返回你可以放置 Alice 和 Bob 的点对数量，使得 Alice 在建造围栏时不会不开心。

注意 Alice 只能建造以 Alice 的位置为左上角、Bob 的位置为右下角的围栏。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：没有办法放置 Alice 和 Bob 使得 Alice 可以建造一个以 Alice 的位置为左上角、Bob 的位置为右下角的围栏。因此我们返回 0。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：有两种放置 Alice 和 Bob 的方式使得 Alice 不会不开心：
- 将 Alice 放在 (4, 4)，Bob 放在 (6, 2)。
- 将 Alice 放在 (2, 6)，Bob 放在 (4, 4)。
你不能将 Alice 放在 (2, 6)，Bob 放在 (6, 2)，因为 (4, 4) 处的人会在围栏内部。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：有两种放置 Alice 和 Bob 的方式使得 Alice 不会不开心：
- 将 Alice 放在 (1, 1)，Bob 放在 (3, 1)。
- 将 Alice 放在 (1, 3)，Bob 放在 (1, 1)。
你不能将 Alice 放在 (1, 3)，Bob 放在 (3, 1)，因为 (1, 1) 处的人会在围栏上。

提示：

  • 2 <= n <= 1000
  • points[i].length == 2
  • -10^9 <= points[i][0], points[i][1] <= 10^9
  • 所有 points[i] 都是不同的。

解题思路

解题思路

这道题要求找到能够放置 Alice 和 Bob 的点对数量，使得以 Alice 为左上角、Bob 为右下角的矩形围栏内没有其他人。

关键观察：

  1. 对于 Alice 在点 (x1, y1)，Bob 在点 (x2, y2)，要构成有效的左上角和右下角关系，必须满足 x1 ≤ x2 且 y1 ≥ y2
  2. 矩形围栏内（包括边界）不能有其他点，即对于任意其他点 (x, y)，不能同时满足 x1 ≤ x ≤ x2 且 y2 ≤ y ≤ y1

优化策略： 根据提示，我们可以先按 x 坐标递增排序，x 坐标相同时按 y 坐标递减排序。这样对于任意 i < j，如果 points[i] 和 points[j] 能构成有效的 Alice-Bob 对，则必须满足 points[i][1] ≥ points[j][1]。

核心算法：

  1. 排序后，对于每个可能的 Alice 位置 points[i]
  2. 遍历所有可能的 Bob 位置 points[j]（其中 j > i 且 points[i][1] ≥ points[j][1]）
  3. 检查矩形内是否有其他点
  4. 为了优化，我们记录已遍历过的点中 y 坐标的最大值，如果这个最大值小于当前 Bob 的 y 坐标，说明矩形内没有其他点

这种方法避免了对每个矩形都进行完整的点检查，大大提高了效率。

代码实现

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int n = points.size();
        
        // 按x坐标升序，x相同时按y坐标降序排序
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) return a[1] > b[1];
            return a[0] < b[0];
        });
        
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int maxY = INT_MIN; // 记录已遍历点中y的最大值
            
            for (int j = i + 1; j < n; j++) {
                // Alice在points[i]，Bob在points[j]
                // 检查是否能构成有效的左上角-右下角关系
                if (points[i][1] >= points[j][1]) {
                    // 检查矩形内是否有其他点
                    // 如果maxY < points[j][1]，说明矩形内没有其他点
                    if (maxY < points[j][1]) {
                        count++;
                    }
                }
                // 更新maxY，但只考虑y坐标不超过points[i][1]的点
                if (points[j][1] <= points[i][1]) {
                    maxY = max(maxY, points[j][1]);
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        n = len(points)
        
        # 按x坐标升序，x相同时按y坐标降序排序
        points.sort(key=lambda p: (p[0], -p[1]))
        
        count = 0
        
        for i in range(n):
            max_y = float('-inf')  # 记录已遍历点中y的最大值
            
            for j in range(i + 1, n):
                # Alice在points[i]，Bob在points[j]
                # 检查是否能构成有效的左上角-右下角关系
                if points[i][1] >= points[j][1]:
                    # 检查矩形内是否有其他点
                    # 如果max_y < points[j][1]，说明矩形内没有其他点
                    if max_y < points[j][1]:
                        count += 1
                
                # 更新max_y，但只考虑y坐标不超过points[i][1]的点
                if points[j][1] <= points[i][1]:
                    max_y = max(max_y, points[j][1])
        
        return count

public class Solution {
    public int NumberOfPairs(int[][] points) {
        int n = points.Length;
        
        // 按x坐标升序，x相同时按y坐标降序排序
        Array.Sort(points, (a, b) => {
            if (a[0] == b[0]) return b[1].CompareTo(a[1]);
            return a[0].CompareTo(b[0]);
        });
        
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int maxY = int.MinValue; // 记录已遍历点中y的最大值
            
            for (int j = i + 1; j < n; j++) {
                // Alice在points[i]，Bob在points[j]
                // 检查是否能构成有效的左上角-右下角关系
                if (points[i][1] >= points[j][1]) {
                    // 检查矩形内是否有其他点
                    // 如果maxY < points[j][1]，说明矩形内没有其他点
                    if (maxY < points[j][1]) {
                        count++;
                    }
                }
                // 更新maxY，但只考虑y坐标不超过points[i][1]的点
                if (points[j][1] <= points[i][1]) {
                    maxY = Math.Max(maxY, points[j][1]);
                }
            }
        }
        
        return count;
    }
}

var numberOfPairs = function(points) {
    const n = points.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i === j) continue;
            
            const [x1, y1] = points[i]; // Alice
            const [x2, y2] = points[j]; // Bob
            
            // Alice must be upper left, Bob must be lower right
            if (x1 > x2 || y1 < y2) continue;
            
            let valid = true;
            
            // Check if any other point is inside or on the fence
            for (let k = 0; k < n; k++) {
                if (k === i || k === j) continue;
                
                const [x, y] = points[k];
                
                // Point is inside or on the fence if x1 <= x <= x2 and y2 <= y <= y1
                if (x >= x1 && x <= x2 && y >= y2 && y <= y1) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(1)

其中 n 是点的数量。排序需要 O(n log n) 时间，双层循环需要 O(n²) 时间，总时间复杂度为 O(n²)。空间复杂度为 O(1)，只使用了常数额外空间。

相关题目