335. 路徑交叉

給你一個整數數組 distance 。

從 X-Y 平面上的點?(0,0)?開始，先向北移動 distance[0] 米，然后向西移動 distance[1] 米，向南移動 distance[2] 米，向東移動 distance[3] 米，持續移動。也就是說，每次移動后你的方位會發生逆時針變化。

判斷你所經過的路徑是否相交。如果相交，返回 true ；否則，返回 false 。

示例 1：

輸入：distance = [2,1,1,2]
輸出：true
示例 2：

輸入：distance = [1,2,3,4]
輸出：false
示例 3：

輸入：distance = [1,1,1,1]
輸出：true

提示：

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

解題思路

分為3種情況討論

1. 外卷
   只要滿足distance[i] > distance[i - 2]這個條件，路徑就會不斷螺旋向外擴展
   

2. 內卷
   只要滿足distance[i] < distance[i - 2]這個條件，路徑就會不斷螺旋向里收縮
   

3. 先外卷再內卷
   由兩部分組成，第一部分是外卷，第二部分是內卷
   當distance[i]>=distance[i-2]-distance[i-4]的時候，如下圖所示，我們需要對i-1的長度進行截斷，因為后面再判斷內卷的時候，不能直接用原來i-1的長度

代碼

class Solution {
public:bool isSelfCrossing(vector<int> &distance) {int i = 2, n = distance.size();if(n<4) return false;while (i < n && distance[i] > distance[i - 2])i++;if (i==n) return false;if (distance[i]>=distance[i-2]-(i>=4?distance[i-4]:0)){distance[i-1]-=(i>=3?distance[i-3]:0);}i++;while (i < n && distance[i] < distance[i - 2])i++;return i!=n;}
};