3025. Find the Number of Ways to Place People I

Leetcode link

题目简介

本题会给我们若干个二维的点，要求我们找到由两个点组成的矩形，这个矩形要满足三点要求：

1. 矩形由右下与左上的点组成
2. 矩形的面积内不允许有其他的点
3. 矩形可以是一条水平或垂直直线

题目要求找出符合条件的矩形个数

解题思路

由于题目要求我们找出矩形左上与右下的点，所以我们可以先给所有的点进行一个排序，排序规则如下：

1. 所有的点按照 x 轴升序排列
2. 如果有 x 轴相同的点，则按照 y 轴降序排列

由此排列之后的点会遵循着由左到右，由上到下的顺序

然后，我们需要一个双层的循环，来遍历图中的点

第一层循环中，我们选取第一个点，由此我们可以知道当前矩形 y 轴的上限就是第一个点的 y 坐标，我们记作 upperYLimit

在第二层循环中，我们遍历下一个点，如果遍历的点的 y 坐标小于等于 upperYLimit，那么就表示我们找到了一个符合的矩形，并将当前的 y 坐标标记为 lowerYLimit

接着我们继续在第二层循环中遍历下一个点，这个点是符合的矩形的要求就是在满足 y 坐标小于等于 upperYLimit 的情况下，y 坐标还要大于 lowerYLimit 否则该点就会出现在上一个矩形中

Javascrip

/**
 * @param {number[][]} points
 * @return {number}
 */
var numberOfPairs = function (points) {
    points.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1]
        }
        return a[0] - b[0]
    })

    let count = 0
    const n = points.length

    for (let i = 0; i < n; i++) {
        const upperYLimit = points[i][1]
        let lowerYLimit = Number.MIN_SAFE_INTEGER

        for (let j = i + 1; j < n; j++) {
            const curY = points[j][1]
            if(curY <= upperYLimit && curY > lowerYLimit) {
                count++
                lowerYLimit = curY

                if(curY === upperYLimit) {
                    break
                }
            }
        }
    }

    return count
};