以下是 LeetCode LCP 15. 游乐园的迷宫 的 Java 实现，基于 贪心 + 向量叉积 的经典解法。
解题思路
核心思想是贪心构造：每一步选择一个"最极端"的点，使得剩余所有未访问的点都在当前方向的同一侧，从而保证后续每一步都能满足转向要求。
1. 起点选择：选择横坐标最小的点（若有多个则选纵坐标最小的），这样可以保证从该点出发，所有其他点都在起点的同一侧
2. 向量叉积判断方向：对于当前点 `now`，候选点 `j`，计算向量 `now→j` 与当前最优向量 `now→best` 的叉积
- 叉积 > 0：`j` 在 `best` 的逆时针方向（左侧）
- 叉积 < 0：`j` 在 `best` 的顺时针方向（右侧）
3. 贪心策略：
- 下一步要左转（`L`）：选择最右侧的点（叉积最小，即顺时针最极端）
- 下一步要右转（`R`）：选择最左侧的点（叉积最大，即逆时针最极端）
```java
import java.util.*;
class Solution {
/**
* 向量叉积：a × b = ax * by - ay * bx
* 叉积 > 0: b 在 a 的逆时针方向（左侧）
* 叉积 < 0: b 在 a 的顺时针方向（右侧）
* 叉积 = 0: 共线（题目保证不存在三点共线）
*/
private long cross(long ax, long ay, long bx, long by) {
return ax * by - ay * bx;
}
public int[] visitOrder(int[][] points, String direction) {
int n = points.length;
int[] ans = new int[n];
boolean[] used = new boolean[n];
// 1. 选择起点：横坐标最小的点（若有多个选纵坐标最小的）
int start = 0;
for (int i = 1; i < n; i++) {
if (points[i][0] < points[start][0] ||
(points[i][0] == points[start][0] && points[i][1] < points[start][1])) {
start = i;
}
}
ans[0] = start;
used[start] = true;
int cur = start; // 当前所在点
// 2. 根据 direction 依次选择下一个点
for (int i = 0; i < n - 2; i++) {
char d = direction.charAt(i);
int next = -1;
long bestX = 0, bestY = 0; // 当前最优向量
for (int j = 0; j < n; j++) {
if (used[j]) continue;
long vx = points[j][0] - points[cur][0];
long vy = points[j][1] - points[cur][1];
if (next == -1) {
// 第一个候选点
next = j;
bestX = vx;
bestY = vy;
continue;
}
long crossVal = cross(bestX, bestY, vx, vy);
if (d == 'L') {
// 下一步要左转，选择最右侧的点（顺时针方向，叉积 < 0）
if (crossVal < 0) {
next = j;
bestX = vx;
bestY = vy;
}
} else {
// 下一步要右转，选择最左侧的点（逆时针方向，叉积 > 0）
if (crossVal > 0) {
next = j;
bestX = vx;
bestY = vy;
}
}
}
ans[i + 1] = next;
used[next] = true;
cur = next;
}
// 3. 最后一个未访问的点
for (int i = 0; i < n; i++) {
if (!used[i]) {
ans[n - 1] = i;
break;
}
}
return ans;
}
}
```
关键点说明
步骤 说明
起点选择 选横坐标最小的点，保证所有其他点都在起点的同一侧（右侧），为后续转向创造条件
叉积判断 `cross(a, b) > 0` 表示 `b` 在 `a` 的左侧（逆时针）；`< 0` 表示在右侧（顺时针）
L 策略 下一步左转 → 选当前点最右侧的点（顺时针最极端），这样剩余点都在该方向的左侧，下一步自然左转
R 策略 下一步右转 → 选当前点最左侧的点（逆时针最极端），这样剩余点都在该方向的右侧，下一步自然右转
最后一点 `direction` 长度为 `n-2`，确定前 `n-1` 个点后，最后剩下 1 个点直接加入
示例验证
```
输入: points = [[1,1],[1,4],[3,2],[2,1]], direction = "LL"
起点: 点0(1,1) — 横坐标最小
→ 第一步 direction[0]='L'，从(1,1)出发选最右侧点
候选: (1,4)向量(0,3), (3,2)向量(2,1), (2,1)向量(1,0)
叉积判断最右侧 → 选点2(3,2)
→ 第二步 direction[1]='L'，从(3,2)出发选最右侧点
候选: (1,4)向量(-2,2), (2,1)向量(-1,-1)
叉积判断最右侧 → 选点1(1,4)
→ 最后剩下点3(2,1)
输出: [0, 2, 1, 3] ✓
```
复杂度分析
- 时间复杂度：O(n²)，每次选择下一个点需要遍历所有未访问点
- 空间复杂度：O(n)，答案数组和访问标记数组
