Kimi LeetCode LCP 15. 游乐园的迷宫 Rust实现

根据已收集的信息我来为你提供 LCP 15. 游乐园的迷宫 的 Rust 实现。题目分析这道题是贪心 计算几何问题。核心思想是 每次选择一个极端的点使得剩余未访问的点全部位于当前转向方向要求的一侧从而保证后续每一步都有可行的选择。核心洞察- 起点选择选择横坐标最小最左侧的点作为起点保证它是凸包上的一个顶点- 转向为 L左转选择相对方向最右的点使得剩余所有点都在当前方向的左侧- 转向为 R右转选择相对方向最左的点使得剩余所有点都在当前方向的右侧向量叉积判断方向对于向量 a (x1, y1) 和 b (x2, y2)- cross(a, b) x1*y2 - y1*x2- cross 0b 在 a 的逆时针方向左侧- cross 0b 在 a 的顺时针方向右侧Rust 实现rustimpl Solution {pub fn visit_order(points: VecVeci32, direction: String) - Veci32 {let n points.len();let dir_chars: Vecchar direction.chars().collect();// 访问标记let mut used vec![false; n];let mut ans: Veci32 Vec::with_capacity(n);// 1. 找最左侧的点作为起点横坐标最小相同则纵坐标最小let mut start 0usize;for i in 1..n {if points[i][0] points[start][0]|| (points[i][0] points[start][0] points[i][1] points[start][1]) {start i;}}used[start] true;ans.push(start as i32);// 2. 贪心根据 direction 依次选择下一个点for d in dir_chars {let mut next: i32 -1;if d L {// 下一步要左转选择相对方向最右的点// 这样剩余所有点都在当前方向的左侧for j in 0..n {if used[j] { continue; }if next -1 {next j as i32;continue;}// 比较向量 (next - start) 和 (j - start) 的叉积// 如果 cross 0说明 j 在 next 的顺时针方向更右let nx points[next as usize][0] - points[start][0];let ny points[next as usize][1] - points[start][1];let jx points[j][0] - points[start][0];let jy points[j][1] - points[start][1];let cross nx * jy - ny * jx;if cross 0 {next j as i32;}}} else {// 下一步要右转选择相对方向最左的点for j in 0..n {if used[j] { continue; }if next -1 {next j as i32;continue;}let nx points[next as usize][0] - points[start][0];let ny points[next as usize][1] - points[start][1];let jx points[j][0] - points[start][0];let jy points[j][1] - points[start][1];let cross nx * jy - ny * jx;if cross 0 {next j as i32;}}}used[next as usize] true;ans.push(next);start next as usize;}// 3. 添加最后一个未访问的点for i in 0..n {if !used[i] {ans.push(i as i32);}}ans}}关键点解释要点 说明起点选择 横坐标最小的点最左侧保证在凸包上后续总能找到满足条件的点L 转向 选最右的点使得剩余点全在当前方向的左侧保证下一步左转可行R 转向 选最左的点使得剩余点全在当前方向的右侧保证下一步右转可行叉积判断 cross(a, b) 0 表示 b 在 a 的顺时针方向更右 0 则更左为什么可行 每次选择极端点后剩余点全在要求的一侧递归下去总有解复杂度分析- 时间复杂度O(N^2)每次选择下一个点需要遍历所有未访问的点- 空间复杂度O(N)用于访问标记和结果数组示例验证示例1points [[1,1],[1,4],[3,2],[2,1]], direction LL- 最左侧点[1,1]索引0- 第一步方向 L从点0出发找最右的点 → 点2 [3,2]- 第二步方向 L从点2出发找最右的点 → 点1 [1,4]- 最后剩余点3 [2,1]- 输出[0, 2, 1, 3] ✓示例2points [[1,3],[2,4],[3,3],[2,1]], direction LR- 最左侧点[1,3]索引0- 第一步方向 L找最右的点 → 点3 [2,1]- 第二步方向 R找最左的点 → 点1 [2,4]- 最后剩余点2 [3,3]- 输出[0, 3, 1, 2] ✓