Hard

题目描述

给你一个整数数组 distance。

从 X-Y 平面上的点 (0, 0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，如此反复。换句话说，每次移动后，移动方向会逆时针变化。

如果你的路径相交了就返回 true，否则返回 false。

示例 1：

输入: distance = [2,1,1,2]
输出: true
解释: 路径在点 (0, 1) 处相交。

示例 2：

输入: distance = [1,2,3,4]
输出: false
解释: 路径不会在任何点相交。

示例 3：

输入: distance = [1,1,1,2,1]
输出: true
解释: 路径在点 (0, 0) 处相交。

提示：

  • 1 <= distance.length <= 10^5
  • 1 <= distance[i] <= 10^5

解题思路

这道题需要判断从原点开始按固定方向（北→西→南→东循环）行进的路径是否会相交。

核心观察： 由于移动方向固定且循环，路径相交只会发生在有限的几种情况下。通过数学分析可以发现，第 i 条线段只可能与第 i-3 或第 i-4 条线段相交。

三种相交情况：

  1. 第四条线与第一条线相交（从第4条线开始检查）

    • 条件：d[i] >= d[i-2] 且 d[i-1] >= d[i-3]

  2. 第五条线与第一条线相交（从第5条线开始检查）

    • 条件：d[i-1] == d[i-3] 且 d[i] + d[i-4] >= d[i-2]

  3. 第六条线与第一条线相交（从第6条线开始检查）

    • 需要满足多个复杂的几何条件

算法思路： 从第4条线段开始，依次检查每条线段是否与之前的线段相交。由于几何约束，只需要检查固定的几种模式即可。

时间复杂度优化： 由于只需检查固定数量的前面线段，每次检查都是常数时间，所以总体时间复杂度为 O(n)。

代码实现

class Solution {
public:
    bool isSelfCrossing(vector<int>& distance) {
        int n = distance.size();
        if (n < 4) return false;
        
        for (int i = 3; i < n; 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-3] >= distance[i-1] && 
                distance[i-1] + distance[i-5] >= distance[i-3] &&
                distance[i] + distance[i-4] >= distance[i-2])
                return true;
        }
        
        return false;
    }
};

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        n = len(distance)
        if n < 4:
            return False
        
        for i in range(3, n):
            # 第四条线与第一条线相交
            if distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3]:
                return True
            
            # 第五条线与第一条线相交
            if (i >= 4 and distance[i-1] == distance[i-3] and 
                distance[i] + distance[i-4] >= distance[i-2]):
                return True
            
            # 第六条线与第一条线相交
            if (i >= 5 and distance[i-2] >= distance[i-4] and 
                distance[i-3] >= distance[i-1] and 
                distance[i-1] + distance[i-5] >= distance[i-3] and
                distance[i] + distance[i-4] >= distance[i-2]):
                return True
        
        return False

public class Solution {
    public bool IsSelfCrossing(int[] distance) {
        int n = distance.Length;
        if (n < 4) return false;
        
        for (int i = 3; i < n; 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-3] >= distance[i-1] && 
                distance[i-1] + distance[i-5] >= distance[i-3] &&
                distance[i] + distance[i-4] >= distance[i-2])
                return true;
        }
        
        return false;
    }
}

var isSelfCrossing = function(distance) {
    const n = distance.length;
    if (n < 4) return false;
    
    for (let i = 3; i < n; i++) {
        // 第四条线与第一条线相交
        if (distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3])
            return true;
        
        // 第五条线与第一条线相交
        if (i >= 4 && distance[i-1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组一次，每次检查都是常数时间
空间复杂度O(1)只使用常数额外空间