LeetCode Record – 2 人员站位的方案数 I

25 – 09 -02

我补药面对计算几何啊 இ д இ

今日份题面：

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

计算点对 (A, B) 的数量，其中

• A 在 B 的左上角，并且
• 它们形成的长方形中（或直线上）没有其它点（包括边界）。

返回数量。

数据范围

• $2\leq n\leq 50$
• $points.length == 2$
• $0\leq points[i][0],points[i][1]\leq 50$
• $points $ 内各点各不相同

理解起来还是相当简单的，要求左上和右下两点构成的矩形内部(含边界)不能有其他点。不过需要注意一下的就是约定只有端点的线段也会被视为有效方案。

一道很明显的计算几何问题，问题是计算几何哪哪都很明显，除了解题方案

虽然这题 $2\leq n\leq 50$ 的数据范围相当小导致暴力 $O(n^3)$ 也能过，但你看标题后面的 I 就知道这玩意八成还有后续(搞不好就是明天每日一题)，而且肯定要扩数据范围，这种情况下 $O(n^3)$ 不优化基本必炸无疑

所以在不考虑暴力的情况下考虑其他解题方案。

说实话开始我是没有明显思路的，但考虑到从左上到右下，为了方便计数总之先排序肯定没错，所以先重写一下 Arrays.sort()方法

Arrays.sort(points, (int[] o1, int[] o2) -> {
    if (o1[0] == o2[0]) return Integer.compare(o2[1], o1[1]);
    return Integer.compare(o1[0], o2[0]);
});

首先按 x 坐标升序排序，如果 x 坐标相同，则按 y 坐标降序排序。这样排序后，对于每个点 A，其后面的点 B 都有 $x \gt A.x$，且如果 x 相同，则 $y\lt A.y$，确保后续遍历时点 B 在点 A 的右下方向。

写到这了没思路了，所以干脆就老方法遍历吧。

• 对于每一个左上角点点 A ，我们遍历它的右边所有点(记当前点点 B )并判断是否能构成满足要求的矩形。
• 此时需要维护一个变量 curHeightLimit ，表示在当前 $[A.x, B.x]$ 的区间内右下角点的最低纵坐标，这很容易理解，因为一旦选择的点纵坐标低于 curHeightLimit ，那么构成的矩形必然包含区间内的某个纵坐标为 curHeightLimit 的点
• 初始化 curHeightLimit 为 Integer.MIN_VALUE
• 对于每个点 B（作为右下角候选），检查：
  • 点 B 的 y 坐标必须小于等于点 A 的 y 坐标（满足左上角关系）。
  • 点 B 的 y 坐标必须大于 curHeightLimit（确保没有其他点存在于矩形内）
• 如果条件均满足，则更新结果，并根据 $B.y$ 更新 curHeightLimit
• 返回最终结果

给出 pass 代码：

class Solution {
    public int numberOfPairs(int[][] points) {
        // 排序，x升序，y降序
        Arrays.sort(points, (int[] o1, int[] o2)->{
            if(o1[0] == o2[0]) return Integer.compare(o2[1], o1[1]);
            return Integer.compare(o1[0], o2[0]);
        });
        int pairs = 0;
        for(int leftup = 0; leftup < points.length; ++leftup){
            int curHeightLimit = Integer.MIN_VALUE;
            for(int rightdown = leftup + 1; rightdown < points.length; ++rightdown){
                // 维护并更新 curHeightLimit 和 pairs
                if(points[rightdown][1] <= points[leftup][1] && points[rightdown][1] > curHeightLimit){
                    ++pairs;
                    curHeightLimit = points[rightdown][1];
                }
            }
        }
        // 返回结果
        return pairs;
    }
}

提交完后想到似乎我们的步骤是针对每个排序后的点对 $(A, B)$ ，查询区间 $(A.x, B.x]$ 内 $y$ 的最高值并将其与$B.y$ 进行比较，区间查询的操作一般优化似乎可以考虑开线段树，这样的时间复杂度似乎可以降到 $)(n \log n)$

是个思路，明天写 II 的时候想想具体的实现方法

By the way 上面的代码对题 II 是能 pass 的，这题没卡数据