Kimi LeetCode 3382. 用点构造面积最大的矩形 II Python3实现
这是 LeetCode 3382. 用点构造面积最大的矩形 II 的 Python3 实现。
问题分析
与 3380 不同，本题数据规模达到 2 \times 10^5，O(n^2) 的暴力枚举会超时。需要使用 线段树（Segment Tree） 优化，将时间复杂度降到 O(n \log n)。
核心思路
将所有点按 (x, y) 排序后，按 x 从小到大扫描。对于当前点作为矩形右上顶点，需要找：
1. 右下顶点：前一个点必须与当前点 x 坐标相同
2. 左上、左下顶点：这两个 y 坐标上，之前最近的点的 x 坐标必须相同
3. 无内部点：矩形内部不能有其他点 → 用线段树维护 y 区间内点的最大 x 坐标
Python3 代码
```python
import bisect
from typing import List
class 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 tree
def update(self, idx, val):
"""单点更新"""
idx = idx + self.length
self.tree[idx] = val
while idx > 1:
self.tree[idx >> 1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])
idx = idx >> 1
def query_range(self, lb, rb):
"""区间查询 [lb, rb] 的最大值"""
if lb > rb:
return -1 # 空区间
lb += self.length
rb += self.length
nodes = []
while lb < rb:
if lb & 1 == 1:
nodes.append(self.tree[lb])
lb += 1
if rb & 1 == 0:
nodes.append(self.tree[rb])
rb -= 1
lb = lb >> 1
rb = rb >> 1
if 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 = -1
for 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 < x1
if 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。