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

以下是 LeetCode 3382. 用点构造面积最大的矩形 II 的 C 语言实现采用 线段树 坐标离散化时间复杂度 O(n \log n)c#include stdlib.h#include string.htypedef 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[i1].x) {int y2_idx find_idx(ys, m, points[i1].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[i1].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)点数组、离散化数组、线段树