以下是 LeetCode LCP 15. 游乐园的迷宫 的 Java 实现基于 贪心 向量叉积 的经典解法。解题思路核心思想是贪心构造每一步选择一个最极端的点使得剩余所有未访问的点都在当前方向的同一侧从而保证后续每一步都能满足转向要求。1. 起点选择选择横坐标最小的点若有多个则选纵坐标最小的这样可以保证从该点出发所有其他点都在起点的同一侧2. 向量叉积判断方向对于当前点 now候选点 j计算向量 now→j 与当前最优向量 now→best 的叉积- 叉积 0j 在 best 的逆时针方向左侧- 叉积 0j 在 best 的顺时针方向右侧3. 贪心策略- 下一步要左转L选择最右侧的点叉积最小即顺时针最极端- 下一步要右转R选择最左侧的点叉积最大即逆时针最极端javaimport 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) {// 下一步要左转选择最右侧的点顺时针方向叉积 0if (crossVal 0) {next j;bestX vx;bestY vy;}} else {// 下一步要右转选择最左侧的点逆时针方向叉积 0if (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)答案数组和访问标记数组