以下是 LeetCode 3382. 用点构造面积最大的矩形 II 的 Rust 实现rustuse std::collections::HashMap;struct SegmentTree {n: usize,tree: Veci32,}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: Veci32, y_coord: Veci32) - 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: Veci32 points.iter().map(|(_, y)| y).collect();ys.sort_unstable();ys.dedup();let m ys.len();let mut y_to_idx: HashMapi32, 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(y11, y2-1) x1 确保内部无点复杂度- 时间O(n \log n)排序 线段树操作- 空间O(n)离散化 线段树