以下是 LeetCode 3382. 用点构造面积最大的矩形 II 的 Java 实现：

解题思路

本题是困难题，核心思路是 排序 + 线段树 + 哈希表：

1. 按x排序：将所有点按 x 坐标排序，x 相同则按 y 排序。

2. 枚举相邻y对：遍历排序后的点，对于同一 x 上的相邻两个点 `(x, y1)` 和 `(x, y2)`，它们可能构成矩形的右边。

3. 找左边界：用 `yToX` 哈希表记录每个 y 值对应的最近左 x 坐标。如果 `y1` 和 `y2` 有相同的左 x 坐标 `L`，则四个角齐全。

4. 判断矩形内无其他点：用 线段树 维护每个 y 值对应的最近左 x 坐标。查询 `(y1, y2)` 开区间内的最大值，如果最大值小于 `L`，说明该区间内没有其他点的 x 坐标在 `[L, x]` 范围内，即矩形内无其他点。

5. 计算面积：若满足条件，面积 = `(y2 - y1) × (x - L)`。

Java 代码

```java
import java.util.*;

class Solution {
    public long maxRectangleArea(int[] xCoord, int[] yCoord) {
        int n = xCoord.length;
        
        // 将点按x坐标排序，x相同则按y排序
        int[][] points = new int[n][2];
        for (int i = 0; i < n; i++) {
            points[i][0] = xCoord[i];
            points[i][1] = yCoord[i];
        }
        Arrays.sort(points, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        
        // y坐标离散化
        TreeSet<Integer> ySet = new TreeSet<>();
        for (int y : yCoord) ySet.add(y);
        List<Integer> ys = new ArrayList<>(ySet);
        int m = ys.size();
        Map<Integer, Integer> yToIndex = new HashMap<>();
        for (int i = 0; i < m; i++) yToIndex.put(ys.get(i), i);
        
        // 线段树：维护每个y值对应的最近左x坐标（初始化为-1）
        SegmentTree tree = new SegmentTree(m, -1);
        
        // 记录每个y值对应的最近左x坐标
        Map<Integer, Integer> yToX = new HashMap<>();
        
        long ans = -1;
        
        // 遍历排序后的点
        int prevX = points[0][0];
        int prevY = points[0][1];
        
        for (int i = 1; i < n; i++) {
            int x = points[i][0];
            int y = points[i][1];
            
            // 如果当前点和前一个点x相同，检查是否能形成矩形
            if (x == prevX) {
                // 检查yToX中prevY和y是否有相同的左x坐标
                if (yToX.containsKey(prevY) && yToX.containsKey(y)) {
                    int xLeft = yToX.get(y);
                    // 需要yToX[prevY]也等于xLeft，即两个y都有相同的左边界
                    if (yToX.get(prevY) == xLeft) {
                        // 用线段树查询(prevY, y)区间内是否有其他点的x > xLeft
                        // 即查询区间最大值，如果最大值 < xLeft，说明矩形内没有其他点
                        int leftIdx = yToIndex.get(prevY) + 1;
                        int rightIdx = yToIndex.get(y) - 1;
                        if (leftIdx <= rightIdx) {
                            int maxX = tree.query(leftIdx, rightIdx);
                            if (maxX < xLeft) {
                                long area = 1L * (y - prevY) * (x - xLeft);
                                ans = Math.max(ans, area);
                            }
                        } else {
                            // 中间没有其他y值，直接计算面积
                            long area = 1L * (y - prevY) * (x - xLeft);
                            ans = Math.max(ans, area);
                        }
                    }
                }
            }
            
            // 更新前一个点的信息
            yToX.put(prevY, prevX);
            tree.update(yToIndex.get(prevY), prevX);
            
            prevX = x;
            prevY = y;
        }
        
        return ans;
    }
}

/**
 * 线段树：维护区间最大值
 */
class SegmentTree {
    private int n;
    private int[] tree;
    private int kInf;
    
    public SegmentTree(int n, int kInf) {
        this.n = n;
        this.kInf = kInf;
        this.tree = new int[4 * n];
        Arrays.fill(tree, kInf);
    }
    
    public void update(int i, int val) {
        update(0, 0, n - 1, i, val);
    }
    
    private void update(int node, int lo, int hi, int i, int val) {
        if (lo == hi) {
            tree[node] = val;
            return;
        }
        int mid = (lo + hi) / 2;
        if (i <= mid) {
            update(2 * node + 1, lo, mid, i, val);
        } else {
            update(2 * node + 2, mid + 1, hi, i, val);
        }
        tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
    }
    
    public int query(int i, int j) {
        return query(0, 0, n - 1, i, j);
    }
    
    private int query(int node, int lo, int hi, int i, int j) {
        if (i <= lo && hi <= j) {
            return tree[node];
        }
        if (j < lo || hi < i) {
            return kInf;
        }
        int mid = (lo + hi) / 2;
        return Math.max(query(2 * node + 1, lo, mid, i, j),
                        query(2 * node + 2, mid + 1, hi, i, j));
    }
}
```

复杂度分析

- 时间复杂度：O(n log n)，其中 n 是点的数量。排序 O(n log n)，线段树操作 O(log n) 每次。
- 空间复杂度：O(n)，用于存储点、离散化映射和线段树。

示例验证

- 示例1：`xCoord = [1,1,3,3], yCoord = [1,3,1,3]`
  - 排序后：`(1,1), (1,3), (3,1), (3,3)`
  - x=1: y=1,3，相邻对(1,3)，yToX为空
  - x=3: y=1,3，相邻对(1,3)，yToX中1→1, 3→1，左边界相同
  - 线段树查询(1,3)区间为空，面积=2×2=4 ✓

- 示例2：`xCoord = [1,1,3,3,2], yCoord = [1,3,1,3,2]`
  - 排序后：`(1,1), (1,3), (2,2), (3,1), (3,3)`
  - x=1: 相邻对(1,3)，yToX为空
  - x=2: 只有一个点，无相邻对
  - x=3: 相邻对(1,3)，yToX中1→1, 3→1
  - 线段树查询(1,3)区间，y=2的位置值为2（来自点(2,2)）
  - maxX=2 > xLeft=1，矩形内有其他点，不合法
  - 返回 -1 ✓

- 示例3：`xCoord = [1,1,3,3,1,3], yCoord = [1,3,1,3,2,2]`
  - 排序后：`(1,1), (1,2), (1,3), (3,1), (3,2), (3,3)`
  - x=1: 相邻对(1,2), (2,3)，yToX为空
  - x=3: 相邻对(1,2), (2,3)
    - (1,2): yToX[1]=1, yToX[2]=1，左边界相同
    - 线段树查询(1,2)区间为空，面积=1×2=2 ✓
    - (2,3): yToX[2]=1, yToX[3]=1，左边界相同
    - 线段树查询(2,3)区间为空，面积=1×2=2

下载文件：[leetcode_3382.java](sandbox:///mnt/agents/output/leetcode_3382.java)