根据已收集的信息，我来为你提供 LCP 15. 游乐园的迷宫 的 Rust 实现。
题目分析
这道题是贪心 + 计算几何问题。核心思想是：
> 每次选择一个"极端"的点，使得剩余未访问的点全部位于当前转向方向要求的一侧，从而保证后续每一步都有可行的选择。
核心洞察
- 起点选择：选择横坐标最小（最左侧）的点作为起点，保证它是凸包上的一个顶点
- 转向为 L（左转）：选择相对方向最右的点，使得剩余所有点都在当前方向的左侧
- 转向为 R（右转）：选择相对方向最左的点，使得剩余所有点都在当前方向的右侧
向量叉积判断方向
对于向量 `a = (x1, y1)` 和 `b = (x2, y2)`：
- `cross(a, b) = x1*y2 - y1*x2`
- `cross > 0`：`b` 在 `a` 的逆时针方向（左侧）
- `cross < 0`：`b` 在 `a` 的顺时针方向（右侧）
Rust 实现
```rust
impl Solution {
pub fn visit_order(points: Vec<Vec<i32>>, direction: String) -> Vec<i32> {
let n = points.len();
let dir_chars: Vec<char> = direction.chars().collect();
// 访问标记
let mut used = vec![false; n];
let mut ans: Vec<i32> = 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)，用于访问标记和结果数组
示例验证
示例1：`points = [[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]` ✓
示例2：`points = [[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]` ✓
