Skip to content

Latest commit

 

History

History

335.Self-Crossing

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

335.Self-Crossing

此题的解法非常精妙。

试想一下,如果这样的操作能够无限进行下去而不相交,那必然是一个螺旋膨胀的图形,需要满足什么条件呢?很简单,只要永远比对面的那个线段更长即可

while (x[i]>x[i-2])
  i++;

一旦这种趋势无法保持,但仍想要不self-crossing的话,那么之后必然形成的是一个螺旋收缩的图形了(因为永远是逆时针地行进)。条件也很简单,只要永远比对面的那个线段更短即可:

while (x[i]<x[i-2])
  i++;

当然这种螺旋收缩的趋势不会是无限的。

但是,对于从膨胀到收缩的临界线段x[i],我们需要有一个额外的判断:

if (x[i]>x[i-2]-x[i-4])
   x[i-1]-=x[i-3];
i++;

以上这步操作其实框定了螺旋收缩的范围。需要仔细体会。

Leetcode Link