这是 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。