企业官网建设流程全解析

LeetCode 335 路径交叉（Self Crossing）题解：O(1) 空间的一趟扫描相交判定算法

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文基于《力扣加加》LeetCode 题解仓库（leetcode）中的 335.self-crossing 题解 展开，深入讲解 LeetCode 335「路径交叉」（Self Crossing）这道 Hard 难度几何题：给定一组长度数组，机器人按"北、西、南、东"逆时针交替行走，如何用一趟扫描、O(1) 空间判断路径是否发生自相交。读完本文，你将掌握"圈形路径自相交"的三种几何判定条件、为何只需观察最近五段路径的核心洞察，以及滚动数组思想在空间优化中的实际应用。

题目背景与题意

• 题目编号：LeetCode 335（路径交叉 / Self Crossing），被收录于本仓库 hard 难度题单 中。
• 题目地址：LeetCode 官方题库（本题最初收录于力扣中国站）。

题目描述

给定一个含有 n 个正数的数组 x。从点 (0,0) 开始，先向北移动 x[0] 米，然后向西移动 x[1] 米，向南移动 x[2] 米，向东移动 x[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

编写一个 O(1) 空间复杂度的一趟扫描算法，判断你所经过的路径是否相交。

示例

示例 1：

┌───┐ │ │ └───┼──> │

输入:[2,1,1,2]输出:true

示例 2：

┌──────┐ │ │ │ │ └────────────>

输入:[1,2,3,4]输出:false

示例 3：

┌───┐ │ │ └───┼>

输入:[1,1,1,1]输出:true

从示例可以看出：路径是一圈一圈向内收缩或向外扩张的"螺旋"，只有当某一段与之前某一段交叉或触碰时才会相交。示例 3 中[1,1,1,1]最后一段恰好触碰到第一段的端点，因此也判定为相交（true）。

前置知识：滚动数组（Rolling Array）

原题解文档将"滚动数组"列为本道题的前置知识。所谓滚动数组，是指当状态转移只依赖最近若干个状态、而与更早的历史状态无关时，不再用完整数组保存全部状态，而是用固定数量的几个变量"滚动"覆盖旧值，从而把空间复杂度从 O(N) 降到 O(1)。

本仓库的 动态规划专题（thinkings/dynamic-programming.md） 以爬楼梯为例给出了经典说明：因为f(n)只与前两个状态f(n-1)、f(n-2)有关，所以只需两个变量a、b交替更新即可，这就是滚动数组的雏形。其本质是：太远的层用不到了，就可以直接抹去。

本题正是这种思想的几何版本——判断最新一段路径是否相交，不必与之前所有段逐一比较，只需要与最近的少数几段比较即可，这就是滚动数组思路在几何问题上的落地。

思路：从 O(B) 朴素解法到 O(1) 滚动优化

朴素做法：动态障碍物集合，空间 O(B)

符合直觉的做法是 O(N) 时间和 O(B) 空间复杂度的算法，其中 B 为"障碍物"的个数，也就是行走过程中经过的坐标点的个数。这种做法与仓库中另一道题 874. 模拟行走机器人（874.walking-robot-simulation） 的思路基本一致：机器人在网格上逐步行走，把已经踩过的坐标点记录为障碍物，每走一步判断下一步是否落在已有障碍物上，若是则说明路径发生了自相交。

区别在于：874 题的障碍物集合是题目预先给定的，而本题的"障碍物"是遍历过程中动态生成的——每遇到一个新坐标点，就将其标记为 obstacle。随着算法进行，obstacles 集合逐渐增大，最终会膨胀到 O(B) 的空间开销，这显然不满足题目 O(1) 空间的要求。

关键洞察：不相交只有两种形态

经过仔细观察可以发现：如果路径一直不相交，从大范围来看只有两种情况：

1. 我们画的圈不断增大（向外扩张的螺旋）；
2. 我们画的圈不断减少（向内收缩的螺旋）。

一旦形态在这两种之间发生切换（比如本来在扩张却突然大幅内收，或本来在收缩却突然外扩），就极有可能触发相交。这个观察把"逐点比较"的笨办法，转化为"仅关注相邻几段长度关系"的局部判定。

核心洞察：只需考虑最近的五段

顺着上面的观察会发现：画最新一笔的时候，并不需要把之前画的所有线段都拿来比较，只需要考虑最近的几个线段即可。原题解指出：实际只需要最近的五个线段。

理由非常巧妙：对最新一段而言，如果它可能与更早的某一段相交，那么一旦与之相交，则必然也一定会与红色标记（最近若干段）部分相交。换句话说，与老线段相交是"被最近几段相交"的必要不充分条件——相交发生的最早时刻，一定落在最近几段的覆盖范围内，因此检查最近五段就足以覆盖所有相交可能性。

旋转不变性：方向无关

画的方向也是不需要考虑的。例如当前画的方向是从左到右，和从上到下，对于"是否相交"的判定没有任何区别——把整幅图顺时针旋转 90 度，相交关系完全不变。方向只是一个坐标系选择问题，判定条件只与长度之间的相对关系有关，因此可以统一按同一套比较逻辑处理四个方向的移动。

相交的三种情形与判定条件

当仔细观察后会发现，相交的情况其实只有以下三种（原题解文档特别注明：图有误，第一种和第二种在换个角度看后是同一种情况，文字解释和代码已更正，因此下面以文字条件为准）：

设当前遍历到第 i 个元素（i 从 0 开始计数）：

情形一（经典夹断相交）

• 条件：x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]
• 含义：最新一段的长度不小于"两段之前"那条与之平行的线段的长度，同时中间一段又足够短，使得最新一段直接"压"到了更早的边上，形成相交。

情形二（端点精确触碰）

• 条件：i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2]
• 含义：最新一段的端点恰好落在"四段之前"那条线段的端点上，属于"刚好碰上"的相交（示例 3 的[1,1,1,1]即属此类，形成└───┼>的形态）。

情形三（较复杂的环绕相交）

• 条件：i > 4，且同时满足x[i] + x[i - 4] >= x[i - 2]、x[i - 1] >= x[i - 3] - x[i - 5]、x[i - 1] <= x[i - 3]、x[i - 2] >= x[i - 4]、x[i - 3] >= x[i - 5]
• 含义：这是一组更"深"的缠绕条件，需要同时用到最近五段（i 到 i-5）的长度关系才能判定，也正是"为什么需要看五段"的原因所在。

其余情况则不相交。

注意循环从i = 3开始：少于四条线段（n < 4）时路径不可能发生自相交，可以直接返回false。

关键点解析

• 一定要画图辅助：这类几何判定题，文字条件很难直接想象，建议按示例把螺旋画出来，标注每段的序号，对照三个条件逐一验证。
• O(1) 空间有固定套路：常见的有两种——
  1. 直接修改原数组（把历史信息就地存储）；
  2. 滚动数组（当前状态并不是和之前所有状态有关，而仅和某几个有关）。
• 本题采用的是滚动数组：判定条件只访问x[i]到x[i-5]六个下标，即只依赖最近六段长度。如果你了解动态规划的滚动数组优化（可参考本仓库 thinkings/dynamic-programming.md 中的滚动数组优化章节），就能理解这里的做法如出一辙。难点在于如何确定当前状态和哪几个历史状态有关——对这道题来说，画图是打开思路的最好方式。
• 面试时先说出 O(B) 的朴素思路，也不失为一个帮助自己冷静分析问题、再逐步优化到 O(1) 的可行策略。

代码实现（Python3）

原题解给出的 Python3 实现如下（已补充注释便于理解）：

class Solution: def isSelfCrossing(self, x: List[int]) -> bool: n = len(x) # 少于四条线段不可能相交 if n < 4: return False for i in range(3, n): # 情形一：最新一段与两段前的平行段夹断相交 if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]: return True # 情形二：端点与四段前的线段端点精确触碰 if i > 3 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] == x[i - 2]: return True # 情形三：较复杂的环绕相交，需要最近五段 if i > 4 and x[i] + x[i - 4] >= x[i - 2] and x[i - 1] >= x[i - 3] - x[i - 5] \ and x[i - 1] <= x[i - 3] and x[i - 2] >= x[i - 4] and x[i - 3] >= x[i - 5]: return True return False

代码要点：

• 一趟for循环完成全部判定，无需额外存储结构；
• 三个判定分支分别对应三种相交情形，命中即返回true；
• 通过下标i-2, i-3, i-4, i-5直接读取历史长度，正是"滚动数组"式的最近状态访问模式；
• 原题解同时感谢了社区成员指出的代码重复判断问题，因此最终版分支条件互斥、无冗余判断。

（注：本题解文档标注的代码支持语言为 Python3，仓库中暂未收录该题的 JavaScript 等其他语言实现；如需验证算法正确性，可将上述代码直接在 Python3 环境中对三组示例输入运行。）

复杂度分析

其中 N 为数组长度：

• 时间复杂度：O(N)，一趟扫描完成判定；
• 空间复杂度：O(1)，只使用常数个额外变量，不随 N 增长。

相关题目与仓库指引

• 朴素思路对照：874. 模拟行走机器人（874.walking-robot-simulation）——同样的"障碍物集合"模型，但障碍物由题目预给定，空间开销天然是 O(B)，可对比体会本题动态障碍物与空间优化的差异。
• 滚动数组理论基础：thinkings/dynamic-programming.md 滚动数组优化章节——解释了"当前状态只与最近若干状态相关"时如何进行空间压缩。
• 题目难度归属：本题位于 hard 难度题单 中。
• 仓库索引：本题解同时被收录于仓库总 README.md 题解索引、SUMMARY.md 目录与 introduction.md 文章列表，读者可在这些索引中按题号快速检索到本文对应章节。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode