人员站位的方案数 II

You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

We define the right direction as positive x-axis (increasing x-coordinate) and the left direction as negative x-axis (decreasing x-coordinate). Similarly, we define the up direction as positive y-axis (increasing y-coordinate) and the down direction as negative y-axis (decreasing y-coordinate)

You have to place n people, including Alice and Bob, at these points such that there is exactly one person at every point. Alice wants to be alone with Bob, so Alice will build a rectangular fence with Alice's position as the upper left corner and Bob's position as the lower right corner of the fence (Note that the fence might not enclose any area, i.e. it can be a line). If any person other than Alice and Bob is either inside the fence or on the fence, Alice will be sad.

Return the number of pairs of points where you can place Alice and Bob, such that Alice does not become sad on building the fence.

Note that Alice can only build a fence with Alice's position as the upper left corner, and Bob's position as the lower right corner. For example, Alice cannot build either of the fences in the picture below with four corners (1, 1), (1, 3), (3, 1), and (3, 3), because:

• With Alice at (3, 3) and Bob at (1, 1), Alice's position is not the upper left corner and Bob's position is not the lower right corner of the fence.
• With Alice at (1, 3) and Bob at (1, 1), Bob's position is not the lower right corner of the fence.

 

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 0
Explanation: There is no way to place Alice and Bob such that Alice can build a fence with Alice's position as the upper left corner and Bob's position as the lower right corner. Hence we return 0. 

Example 2:

Input: points = [[6,2],[4,4],[2,6]]
Output: 2
Explanation: There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (4, 4) and Bob at (6, 2).
- Place Alice at (2, 6) and Bob at (4, 4).
You cannot place Alice at (2, 6) and Bob at (6, 2) because the person at (4, 4) will be inside the fence.

Example 3:

Input: points = [[3,1],[1,3],[1,1]]
Output: 2
Explanation: There are two ways to place Alice and Bob such that Alice will not be sad:
- Place Alice at (1, 1) and Bob at (3, 1).
- Place Alice at (1, 3) and Bob at (1, 1).
You cannot place Alice at (1, 3) and Bob at (3, 1) because the person at (1, 1) will be on the fence.
Note that it does not matter if the fence encloses any area, the first and second fences in the image are valid.

 

Constraints:

• 2 <= n <= 1000
• points[i].length == 2
• -109 <= points[i][0], points[i][1] <= 109
• All points[i] are distinct.

import java.util.*;
import java.util.stream.*;

// 思路：
// 使用流的方式来实现与上述Java代码同样的逻辑。
public class Solution {
    public int numOfWays(int[][] points) {
        int n = points.length;
        return (int) IntStream.range(0, n).boxed()
            .flatMap(i -> IntStream.range(0, n).filter(j -> j != i).mapToObj(j -> new int[]{i, j}))
            .filter(pair -> {
                int x1 = points[pair[0]][0], y1 = points[pair[0]][1];
                int x2 = points[pair[1]][0], y2 = points[pair[1]][1];
                return x1 < x2 && y1 > y2;
            })
            .filter(pair -> {
                int x1 = points[pair[0]][0], y1 = points[pair[0]][1];
                int x2 = points[pair[1]][0], y2 = points[pair[1]][1];
                return IntStream.range(0, n)
                    .filter(k -> k != pair[0] && k != pair[1])
                    .noneMatch(k -> {
                        int x = points[k][0], y = points[k][1];
                        return x1 <= x && x <= x2 && y2 <= y && y <= y1;
                    });
            })
            .count();
    }
}

解题思路基于排序和迭代搜索的组合。首先，将点按x坐标升序排序，如果x坐标相同，则按y坐标降序排序。这样排序后，对于任意点Alice，所有在其右边的点都是可能的Bob的候选者。接着，遍历每个点作为Alice，对于每个Alice，检查它右边的点作为Bob是否满足条件（即没有其他点在Alice和Bob所形成的矩形区域内）。为了快速判断，使用变量min_y记录遍历过程中遇到的最小y坐标值（即Bob的y坐标必须大于等于这个值，同时小于等于Alice的y坐标），这样可以确保在Alice的右下方的所有点都不会在所形成的矩形内。

O(n^2)

O(1)