Leetcode3027. 人员站位的方案数 II

本文主要是介绍Leetcode3027. 人员站位的方案数 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

题目来源：3027. 人员站位的方案数 II

解法1：暴力

暴力枚举 liupengsay 和小羊肖恩的位置，当 liupengsay 和小羊肖恩的位置满足要求（liupengsay 建立的围栏必须确保 liupengsay 的位置是矩形的左上角，小羊肖恩的位置是矩形的右下角）时，再次遍历数组 points，判断其余点是否会落在 liupengsay 建立的围栏内，若不会，计数器 count 自增 1。

代码：

/** @lc app=leetcode.cn id=3027 lang=cpp** [3027] 人员站位的方案数 II*/// @lc code=start
class Solution
{
public:int numberOfPairs(vector<vector<int>> &points){int n = points.size();int count = 0;for (int i = 0; i < n; i++){int x1 = points[i][0], y1 = points[i][1];for (int j = 0; j < n; j++){if (i == j)continue;int x2 = points[j][0], y2 = points[j][1];if (x1 <= x2 && y1 >= y2) // 围栏合法{bool ok = true;for (int k = 0; k < n; k++){if (k == i || k == j)continue;int x = points[k][0], y = points[k][1];if (x >= x1 && x <= x2 && y >= y2 && y <= y1){ok = false;break;}}if (ok)count++;}}}return count;}
};
// @lc code=end

结果：

超时。

在这里插入图片描述

复杂度分析：

时间复杂度：O(n³)，其中 n 是数组 points 的元素个数。

空间复杂度：O(1)。

解法2：排序 + 枚举

将 points 按照横坐标从小到大排序，横坐标相同的，按照纵坐标从大到小排序。

如此一来，在枚举 points[i] 和 points[j] 时（i<j），就只需要关心纵坐标的大小。

固定 points[i]，然后枚举 points[j]：

如果 points[j][1] 比之前枚举的点的纵坐标都大，那么矩形内没有其它点，符合要求，答案加 1。
如果 points[j][1] 小于等于之前枚举的某个点的纵坐标，那么矩形内有其它点，不符合要求。

所以在枚举 points[j] 的同时，需要维护纵坐标的最大值 maxY。这也解释了为什么横坐标相同的，按照纵坐标从大到小排序。这保证了横坐标相同时，我们总是优先枚举更靠上的点，不会误把包含其它点的矩形也当作符合要求的矩形。

最后返回答案。

代码：

/** @lc app=leetcode.cn id=3027 lang=cpp** [3027] 人员站位的方案数 II*/// @lc code=start// 排序 + 枚举class Solution
{
public:int numberOfPairs(vector<vector<int>> &points){sort(points.begin(), points.end(), [](const auto &p, const auto &q){ return p[0] != q[0] ? p[0] < q[0] : p[1] > q[1]; });int n = points.size();int count = 0;for (int i = 0; i < n; i++){int y0 = points[i][1];int max_y = INT_MIN;for (int j = i + 1; j < n; j++){int y = points[j][1];if (y <= y0 && y > max_y){max_y = y;count++;}}}return count;}
};
// @lc code=end