以下是 LeetCode 3464 的 Rust 实现核心思路是二分答案 单调队列优化 DP。解题思路1. 二分答案答案范围是 [0, \text{side}]对最小曼哈顿距离进行二分搜索2. 展开正方形将正方形边界按顺时针展开为一维序列按边分类排序3. 可行性检验对于候选距离 d用单调队列优化的 DP 判断能否选出 k 个点使得相邻点间曼哈顿距离 \ge d完整代码rustuse std::collections::VecDeque;impl Solution {pub fn max_distance(side: i32, points: VecVeci32, k: i32) - i32 {let ordered Self::get_ordered_points(side, points);let mut l 0;let mut r side;while l r {let m (l r 1) / 2;if Self::is_valid_distance(ordered, k, m) {l m;} else {r m - 1;}}l}// 判断能否选出 k 个点使得相邻点间曼哈顿距离 dfn is_valid_distance(ordered: [(i32, i32)], k: i32, d: i32) - bool {let mut dq: VecDequeSequence VecDeque::new();dq.push_back(Sequence::new(ordered[0].0, ordered[0].1,ordered[0].0, ordered[0].1, 1));let mut max_length 1;for i in 1..ordered.len() {let (x, y) ordered[i];let mut start_x x;let mut start_y y;let mut length 1;// 维护单调队列保留能作为起点的序列while let Some(first) dq.front() {if Self::manhattan(x, y, first.end_x, first.end_y) d {if Self::manhattan(x, y, first.start_x, first.start_y) d first.length 1 length {start_x first.start_x;start_y first.start_y;length first.length 1;max_length max_length.max(length);}dq.pop_front();} else {break;}}dq.push_back(Sequence::new(start_x, start_y, x, y, length));}max_length k}// 曼哈顿距离fn manhattan(x1: i32, y1: i32, x2: i32, y2: i32) - i32 {(x1 - x2).abs() (y1 - y2).abs()}// 将正方形边界上的点按顺时针顺序展开fn get_ordered_points(side: i32, points: [Veci32]) - Vec(i32, i32) {let mut left: Vec(i32, i32) Vec::new();let mut top: Vec(i32, i32) Vec::new();let mut right: Vec(i32, i32) Vec::new();let mut bottom: Vec(i32, i32) Vec::new();for point in points {let x point[0];let y point[1];if x 0 y 0 {left.push((x, y));} else if x 0 y side {top.push((x, y));} else if x side y side {right.push((x, y));} else {bottom.push((x, y));}}// 按顺时针方向排序各边上的点left.sort_by_key(|p| p.1); // 左y 从小到大top.sort_by_key(|p| p.0); // 上x 从小到大right.sort_by(|a, b| b.1.cmp(a.1)); // 右y 从大到小bottom.sort_by(|a, b| b.0.cmp(a.0)); // 下x 从大到小let mut ordered Vec::new();ordered.extend(left);ordered.extend(top);ordered.extend(right);ordered.extend(bottom);ordered}}// 记录序列信息struct Sequence {start_x: i32, start_y: i32, // 序列起点end_x: i32, end_y: i32, // 序列终点length: i32, // 序列长度包含的点数}impl Sequence {fn new(start_x: i32, start_y: i32, end_x: i32, end_y: i32, length: i32) - Self {Self { start_x, start_y, end_x, end_y, length }}}关键点说明要点 说明二分答案 经典最大化最小值问题答案范围 [0, \text{side}]k \ge 4 时答案不超过 \text{side}展开正方形 按顺时针将边界点排成一维序列左(y↑)、上(x↑)、右(y↓)、下(x↓)单调队列优化 DP 状态 dp[i] 表示以第 i 个点结尾的最长合法序列长度。利用单调性队首维护最优起点可行性检验 对于候选距离 d检查是否存在长度 \ge k 的合法序列复杂度分析- 时间复杂度O(n \log \text{side})其中 n \text{points.len()}。二分搜索 O(\log \text{side})每次检验 O(n)- 空间复杂度O(n)