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

这是 LeetCode 3382. 用点构造面积最大的矩形 II 的 Python3 实现。问题分析与 3380 不同本题数据规模达到 2 \times 10^5O(n^2) 的暴力枚举会超时。需要使用 线段树Segment Tree 优化将时间复杂度降到 O(n \log n)。核心思路将所有点按 (x, y) 排序后按 x 从小到大扫描。对于当前点作为矩形右上顶点需要找1. 右下顶点前一个点必须与当前点 x 坐标相同2. 左上、左下顶点这两个 y 坐标上之前最近的点的 x 坐标必须相同3. 无内部点矩形内部不能有其他点 → 用线段树维护 y 区间内点的最大 x 坐标Python3 代码pythonimport bisectfrom typing import Listclass SegmentTree:def __init__(self, arr):self.length len(arr)self.tree self.build(arr)def feature_func(self, *args):取最大值return max(args)def build(self, arr):n len(arr)tree [0 for _ in range(2 * n)]for i in range(n):tree[i n] arr[i]for i in range(n - 1, 0, -1):tree[i] self.feature_func(tree[i 1], tree[(i 1) | 1])return treedef update(self, idx, val):单点更新idx idx self.lengthself.tree[idx] valwhile idx 1:self.tree[idx 1] self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx idx 1def query_range(self, lb, rb):区间查询 [lb, rb] 的最大值if lb rb:return -1 # 空区间lb self.lengthrb self.lengthnodes []while lb rb:if lb 1 1:nodes.append(self.tree[lb])lb 1if rb 1 0:nodes.append(self.tree[rb])rb - 1lb lb 1rb rb 1if lb rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)def query(self, idx):单点查询return self.tree[idx self.length]class Solution:def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) - int:points [(x, y) for x, y in zip(xCoord, yCoord)]n len(points)points sorted(points)# y坐标离散化cols sorted(set(yCoord))# 线段树维护每个y坐标上已处理点的最大x坐标初始为-1表示无点closest SegmentTree([-1 for _ in cols])ans -1for i in range(n - 1):y1_idx bisect.bisect_left(cols, points[i][1])# 当前点和下一个点x坐标相同可能作为矩形的右侧边if points[i][0] points[i 1][0]:y2_idx bisect.bisect_left(cols, points[i 1][1])# 查询两个y坐标上之前最近的点的x坐标x1 closest.query(y1_idx)x2 closest.query(y2_idx)# 左侧两个顶点的x坐标必须相同if x1 ! -1 and x2 ! -1 and x1 x2:# 计算面积S (points[i 1][1] - points[i][1]) * (points[i][0] - x1)# 检查矩形内部是否无其他点# y1_idx 和 y2_idx 之间的所有点x坐标必须都 x1# 即区间最大x x1if y2_idx - y1_idx 1 or closest.query_range(y1_idx 1, y2_idx - 1) x1:ans max(ans, S)# 处理完当前点后将其加入线段树closest.update(y1_idx, points[i][0])return ans复杂度分析- 时间复杂度O(n \log n)排序 O(n \log n)每次线段树操作 O(\log n)- 空间复杂度O(n)离散化数组和线段树关键要点1. 扫描线思想按 x 排序后已处理的点都在当前点左侧2. 线段树维护每个 y 坐标上已处理点的最大 x 坐标3. 矩形验证通过查询 (y_1, y_2) 区间内的最大 x 坐标判断矩形内部是否为空4. 面积最大化由于按 x 从小到大扫描且优先找最近的左侧点面积大的会被自然考虑此解法在 LeetCode 上可以通过耗时约 3270ms。