LeetCode 335. 路径交叉

2024-08-14 HGNULB 约 5 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 335. 路径交叉

题意分析

给一个正整数数组 x，从原点出发，按「北、西、南、东」的固定循环依次走 x[0]、x[1]、x[2]…… 每一步的长度由数组给出，方向由下标模 4 决定。问这条折线是否与自身相交（含端点接触）。

方向序列是逆时针固定循环的，这是全题最强的约束。它意味着路径不可能是任意折线，而是一条不断左转 90 度的「螺旋」。任何两条不相邻的边要么平行、要么垂直，而且相对位置被转向规律锁死。

边长都是正数，所以不会出现原地不动的退化边，相邻两边必然垂直，相邻边之间不可能相交（只共享一个端点，那不算自交）。因此可能相交的最近一对是当前边与三条之前的边。

关键的结构性洞察藏在这个螺旋里：由于方向永远逆时针旋转，路径要么持续向外扩张、要么持续向内收缩。一旦从扩张转为收缩，它就开始向内绕，此时才可能撞上早先画过的边；而在持续扩张阶段，每条新边都跑得比前面更远，永远撞不上任何旧边。这解释了为什么不需要拿当前边去和所有历史边比较——只需要和最近的几条比。

数据规模上，x 的长度可达 $10^5$，所以 $O(n^2)$ 的两两线段求交（约 $10^{10}$ 次判定）不可行，必须做到 $O(n)$。这条规模限制正是「必须找出常数条判定形态」的信号。

边界：长度小于 4 时不可能自交（相邻边只共享端点），所以循环从下标 3 开始；判定条件里会用到 x[i-4]、x[i-5]，因此第二、三种形态分别要等到 i >= 4、i >= 5 才能检查。

解法：几何分情况判交

核心思路

路径方向固定按北、西、南、东循环。由于每条边与更早边的相对方向受限，第一次发生自交时，当前第 i 条边只可能碰到第 i-3、i-4 或 i-5 条边；若能碰到更早的边，必先穿过这三条近邻中的一条。

因而只需检查三种局部形态：

普通穿越 i-3： x[i]>=x[i-2] 且 x[i-1]<=x[i-3]。

共线覆盖 i-4： i>=4，x[i-1]==x[i-3] 且 x[i]+x[i-4]>=x[i-2]。

内缩时穿越 i-5： i>=5，同时满足 x[i-2]>=x[i-4]、x[i]+x[i-4]>=x[i-2]、x[i-1]<=x[i-3]、x[i-1]+x[i-5]>=x[i-3]。

比较都保留等号，因为端点接触和线段重合也属于相交。

正确性说明：循环不变量是，进入下标 i 的检查前，前 i 条边互不相交；若加入当前边产生第一次相交，它必属于上述三类之一。任一条件命中时对应两条线段确实接触或重叠；扫描结束仍未命中则不存在自交。循环每轮前进一条边，必在有限步内终止。

解题步骤

从 i=3 开始扫描；更少的边不可能与非相邻旧边相交。

无条件检查与 i-3 的普通穿越。

在 i>=4 时检查与 i-4 的共线覆盖。

在 i>=5 时检查与 i-5 的复杂内缩。

三类都未出现则继续，最终返回 false。

[2,1,1,2] 命中第一类；[1,1,2,1,1] 命中第二类；[1,1,2,2,1,1] 命中第三类且以端点接触。持续扩张的 [1,2,3,4] 不满足任何条件。

代码实现

class Solution {
    public boolean isSelfCrossing(int[] distance) {
        for (int i = 3; i < distance.length; i++) {
            if (distance[i] >= distance[i - 2]
                    && distance[i - 1] <= distance[i - 3]) {
                return true;
            }

            if (i >= 4
                    && distance[i - 1] == distance[i - 3]
                    && distance[i] + distance[i - 4] >= distance[i - 2]) {
                return true;
            }

            if (i >= 5
                    && distance[i - 2] >= distance[i - 4]
                    && distance[i] + distance[i - 4] >= distance[i - 2]
                    && distance[i - 1] <= distance[i - 3]
                    && distance[i - 1] + distance[i - 5] >= distance[i - 3]) {
                return true;
            }
        }
        return false;
    }
}

func isSelfCrossing(distance []int) bool {
	for i := 3; i < len(distance); i++ {
		if distance[i] >= distance[i-2] &&
			distance[i-1] <= distance[i-3] {
			return true
		}

		if i >= 4 &&
			distance[i-1] == distance[i-3] &&
			distance[i]+distance[i-4] >= distance[i-2] {
			return true
		}

		if i >= 5 &&
			distance[i-2] >= distance[i-4] &&
			distance[i]+distance[i-4] >= distance[i-2] &&
			distance[i-1] <= distance[i-3] &&
			distance[i-1]+distance[i-5] >= distance[i-3] {
			return true
		}
	}
	return false
}

复杂度分析

时间复杂度： $O(n)$，每条边只做常数次比较。

空间复杂度： $O(1)$。

关键点总结

固定逆时针方向把全局线段求交压缩成三种局部形态。

三类分别覆盖与 i-3、i-4、i-5 的第一次相交，缺一不可。

接触也算相交，因此边界比较必须包含等号。

下标保护既防越界，也对应各形态所需的最少边数。

易错点总结

只检查第一类： 会漏掉 [1,1,2,1,1] 的共线覆盖。

漏掉第三类： [1,1,2,2,1,1] 会被错判为不相交。

把第二类的相等放宽为小于等于： 两条平行边未必共线，会产生误报。

使用严格不等号： 会漏掉端点刚好接触的情况。

缺少 i>=4、i>=5 保护： 短数组会访问负下标。

相似题目

题目	难度	考察点
874. 模拟行走机器人	中等	方向由指令动态决定而非固定循环，只能老实模拟，障碍物查询靠哈希集合
1041. 困于环中的机器人	中等	同样利用「方向循环」的周期性，靠一轮指令后的净位移与朝向判断是否成环
836. 矩形重叠	简单	轴对齐图形相交判定的最小载体，练习「投影到每一维分别判区间是否相交」
223. 矩形面积	中等	在相交判定之上还要算重叠面积，考察容斥与重叠区间长度的计算
391. 完美矩形	困难	判断若干小矩形能否恰好拼成大矩形，靠面积和 + 角点出现次数的奇偶性
149. 直线上最多的点数	困难	几何共线判定，重点在用最简分数表示斜率以避免浮点误差
54. 螺旋矩阵	中等	同为逆时针 / 顺时针螺旋结构，但靠四个边界变量显式收缩，可对照本题的隐式判定