以下是 LeetCode 3382. 用点构造面积最大的矩形 II 的 Rust 实现：
```rust
use std::collections::HashMap;
struct SegmentTree {
n: usize,
tree: Vec<i32>,
}
impl SegmentTree {
fn new(n: usize) -> Self {
SegmentTree {
n,
tree: vec![-1; 2 * n],
}
}
fn update(&mut self, idx: usize, val: i32) {
let mut i = idx + self.n;
self.tree[i] = val;
while i > 1 {
i >>= 1;
self.tree[i] = self.tree[i << 1].max(self.tree[(i << 1) | 1]);
}
}
fn query(&self, idx: usize) -> i32 {
self.tree[idx + self.n]
}
fn query_range(&self, mut l: usize, mut r: usize) -> i32 {
if l > r {
return -1;
}
l += self.n;
r += self.n;
let mut res = -1;
while l <= r {
if l & 1 == 1 {
res = res.max(self.tree[l]);
l += 1;
}
if r & 1 == 0 {
res = res.max(self.tree[r]);
r -= 1;
}
l >>= 1;
r >>= 1;
}
res
}
}
impl Solution {
pub fn max_rectangle_area(x_coord: Vec<i32>, y_coord: Vec<i32>) -> i64 {
let n = x_coord.len();
let mut points: Vec<(i32, i32)> = x_coord.into_iter()
.zip(y_coord.into_iter())
.collect();
points.sort_unstable();
// y 坐标离散化
let mut ys: Vec<i32> = points.iter().map(|&(_, y)| y).collect();
ys.sort_unstable();
ys.dedup();
let m = ys.len();
let mut y_to_idx: HashMap<i32, usize> = HashMap::with_capacity(m);
for (i, &y) in ys.iter().enumerate() {
y_to_idx.insert(y, i);
}
let mut seg = SegmentTree::new(m);
let mut ans: i64 = -1;
for i in 0..n - 1 {
let y1 = points[i].1;
let y1_idx = *y_to_idx.get(&y1).unwrap();
// 相邻两点 x 相同，可能构成矩形右侧边
if points[i].0 == points[i + 1].0 {
let y2 = points[i + 1].1;
let y2_idx = *y_to_idx.get(&y2).unwrap();
let x1 = seg.query(y1_idx);
let x2 = seg.query(y2_idx);
// 左侧两个顶点的 x 坐标必须相同
if x1 != -1 && x2 != -1 && x1 == x2 {
let area = (y2 as i64 - y1 as i64) * (points[i].0 as i64 - x1 as i64);
// 检查矩形内部是否无其他点
if y2_idx - y1_idx <= 1 || seg.query_range(y1_idx + 1, y2_idx - 1) < x1 {
ans = ans.max(area);
}
}
}
// 将当前点加入线段树
seg.update(y1_idx, points[i].0);
}
ans
}
}
```
关键点说明
要点 说明
离散化 用 `HashMap` 将 y 坐标映射到 0m-1 的索引
线段树 迭代式实现（数组下标从 n 开始），维护每个 y 上已处理点的最大 x
扫描顺序 按 x 排序后从小到大扫描，保证已处理点都在当前点左侧
面积类型 使用 `i64` 避免乘法溢出
矩形验证 `query_range(y1+1, y2-1) < x1` 确保内部无点
复杂度
- 时间：O(n \log n)（排序 + 线段树操作）
- 空间：O(n)（离散化 + 线段树）
