Kimi LeetCode 3382. 用点构造面积最大的矩形 II C语言实现

以下是 LeetCode 3382. 用点构造面积最大的矩形 II 的 C 语言实现，采用 线段树 + 坐标离散化，时间复杂度 O(n \log n)：

```c
#include <stdlib.h>
#include <string.h>

typedef struct {
int x;
int y;
} Point;

/* 按 x 排序，x 相同按 y 排序 */
int cmp_point(const void *a, const void *b) {
Point *p1 = (Point*)a;
Point *p2 = (Point*)b;
if (p1->x != p2->x) return p1->x - p2->x;
return p1->y - p2->y;
}

int cmp_int(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}

/* 二分查找 y 在离散化数组中的索引 */
int find_idx(int *ys, int n, int y) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (ys[mid] == y) return mid;
if (ys[mid] < y) l = mid + 1;
else r = mid - 1;
}
return -1;
}

/* 不小于 x 的最小 2 的幂 */
int next_pow2(int x) {
int n = 1;
while (n < x) n <<= 1;
return n;
}

/* 迭代式线段树，维护区间最大值 */
typedef struct {
int n; // 扩展为 2 的幂后的大小
int *tree;
} SegTree;

SegTree* seg_tree_create(int size) {
SegTree *st = (SegTree*)malloc(sizeof(SegTree));
st->n = next_pow2(size);
st->tree = (int*)malloc(sizeof(int) * 2 * st->n);
for (int i = 0; i < 2 * st->n; i++) st->tree[i] = -1;
return st;
}

void seg_tree_free(SegTree *st) {
free(st->tree);
free(st);
}

void seg_tree_update(SegTree *st, int pos, int val) {
int i = pos + st->n;
st->tree[i] = val;
for (i >>= 1; i > 0; i >>= 1) {
int left = st->tree[i << 1];
int right = st->tree[(i << 1) | 1];
st->tree[i] = left > right ? left : right;
}
}

/* 查询 [l, r) 区间最大值，左闭右开 */
int seg_tree_query_range(SegTree *st, int l, int r) {
if (l >= r) return -1;
int res = -1;
l += st->n;
r += st->n;
while (l < r) {
if (l & 1) {
if (st->tree[l] > res) res = st->tree[l];
l++;
}
if (r & 1) {
r--;
if (st->tree[r] > res) res = st->tree[r];
}
l >>= 1;
r >>= 1;
}
return res;
}

int seg_tree_query_point(SegTree *st, int pos) {
return st->tree[pos + st->n];
}

/* LeetCode 函数签名 */
long long maxRectangleArea(int* xCoord, int xCoordSize, int* yCoord, int yCoordSize) {
int n = xCoordSize;
Point *points = (Point*)malloc(sizeof(Point) * n);
for (int i = 0; i < n; i++) {
points[i].x = xCoord[i];
points[i].y = yCoord[i];
}

qsort(points, n, sizeof(Point), cmp_point);

/* y 坐标离散化 */
int *ys = (int*)malloc(sizeof(int) * n);
memcpy(ys, yCoord, sizeof(int) * n);
qsort(ys, n, sizeof(int), cmp_int);
int m = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || ys[i] != ys[i-1]) ys[m++] = ys[i];
}

SegTree *st = seg_tree_create(m);
long long ans = -1;

for (int i = 0; i < n - 1; i++) {
int y1_idx = find_idx(ys, m, points[i].y);

/* 相邻两点 x 相同，可能构成矩形右侧边 */
if (points[i].x == points[i+1].x) {
int y2_idx = find_idx(ys, m, points[i+1].y);
int x1 = seg_tree_query_point(st, y1_idx);
int x2 = seg_tree_query_point(st, y2_idx);

/* 左侧两个顶点的 x 坐标必须相同 */
if (x1 != -1 && x2 != -1 && x1 == x2) {
long long h = (long long)points[i+1].y - points[i].y;
long long w = (long long)points[i].x - x1;
long long area = h * w;

/* 检查矩形内部是否无其他点：区间 (y1, y2) 内所有点的 x 均 < x1 */
if (y2_idx - y1_idx <= 1 || seg_tree_query_range(st, y1_idx + 1, y2_idx) < x1) {
if (area > ans) ans = area;
}
}
}

/* 将当前点加入线段树 */
seg_tree_update(st, y1_idx, points[i].x);
}

seg_tree_free(st);
free(points);
free(ys);
return ans;
}
```

关键点说明

要点 说明
排序扫描 按 `x` 排序后从小到大扫描，保证已处理点都在当前点左侧
离散化 `qsort` + 去重后用二分查找（`bsearch` 手动实现）将 `y` 映射到索引
线段树 迭代式实现，将大小扩展至最近的 2 的幂，确保区间查询正确性
区间查询 采用左闭右开 `[l, r)` 语义，查询 `(y1, y2)` 内部是否有 `x ≥ x1` 的点
面积计算 使用 `long long` 避免 `int` 乘法溢出

复杂度

- 时间：O(n \log n)（排序 + 每次线段树操作）
- 空间：O(n)（点数组、离散化数组、线段树）