千问 LeetCode 3027. 人员站位的方案数 II C语言实现

针对 LeetCode 3027. 人员站位的方案数 II，由于点的数量 n 最大可达 1000，如果采用 O(n^3) 的暴力枚举方法会超时。最优的解法是采用 排序 + 枚举，将时间复杂度优化至 O(n^2)。

核心思路
1. 排序规则：将所有的点按照横坐标 x 从小到大排序；如果横坐标相同，则按照纵坐标 y 从大到小排序。
2. 枚举左上角：外层循环遍历排序后的点，将其作为 Alice 的位置（即矩形的左上角）。
3. 枚举右下角：内层循环向后遍历，寻找 Bob 的位置（即矩形的右下角）。为了保证矩形内部和边缘没有其他点，Bob 的纵坐标必须小于等于 Alice 的纵坐标，并且 Bob 的纵坐标必须严格大于之前枚举过的所有右下角点的纵坐标（维护一个当前最大纵坐标 max_y）。

C语言实现代码

#include <stdlib.h>
#include <limits.h>

// 比较函数：按 x 升序排序，x 相同时按 y 降序排序
int cmp(const void *a, const void *b) {
int *p1 = *(int **)a;
int *p2 = *(int **)b;
if (p1[0] != p2[0]) {
return p1[0] - p2[0];
}
return p2[1] - p1[1];
}

int numberOfPairs(int** points, int pointsSize, int* pointsColSize) {
// 1. 对点进行排序
qsort(points, pointsSize, sizeof(int *), cmp);

int ans = 0;

// 2. 枚举左上角的点 (Alice)
for (int i = 0; i < pointsSize; i++) {
int y_alice = points[i][1];
int max_y = INT_MIN; // 记录当前枚举过程中，右下角点的最大纵坐标

// 3. 枚举右下角的点 (Bob)
for (int j = i + 1; j < pointsSize; j++) {
int y_bob = points[j][1];

// Bob 必须在 Alice 的下方或同一水平线，且纵坐标大于之前记录的最大纵坐标
// 这样能保证矩形内和边界上除了 Alice 和 Bob 没有其他点
if (y_bob <= y_alice && y_bob > max_y) {
ans++;
max_y = y_bob; // 更新最大纵坐标
}
}
}

return ans;
}

复杂度分析
* 时间复杂度：O(n^2)，其中 n 是数组 points 的长度。排序的时间复杂度为 O(n log n)，双重循环枚举点对的时间复杂度为 O(n^2)，整体由 O(n^2) 主导。
* 空间复杂度：O(log n)，主要为 qsort 排序时使用的栈空间。