Kimi LeetCode 3464. 正方形上的点之间的最大距离 Rust实现
以下是 LeetCode 3464 的 Rust 实现，核心思路是二分答案 + 单调队列优化 DP。
解题思路
1. 二分答案：答案范围是 [0, \text{side}]，对最小曼哈顿距离进行二分搜索
2. 展开正方形：将正方形边界按顺时针展开为一维序列，按边分类排序
3. 可行性检验：对于候选距离 d，用单调队列优化的 DP 判断能否选出 k 个点，使得相邻点间曼哈顿距离 \ge d
完整代码
```rust
use std::collections::VecDeque;
impl Solution {
pub fn max_distance(side: i32, points: Vec<Vec<i32>>, 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 个点，使得相邻点间曼哈顿距离 >= d
fn is_valid_distance(ordered: &[(i32, i32)], k: i32, d: i32) -> bool {
let mut dq: VecDeque<Sequence> = 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: &[Vec<i32>]) -> 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)