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

通过画图分析可以得知,要想不相交,就只有三种模式:

  1. 不断地螺旋形膨胀,时刻满足 x[i]>x[i-2]

  2. 不断地螺旋形收缩,时刻满足 x[i]<x[i-2]

  3. 先螺旋膨胀,再螺旋收缩。假设其中的转折点是x[i],即第i步是第一次出现x[i]<x[i-2]的线段。根据之前的分析,从i+1开始,就进入了螺旋收缩模式,需要时刻满足 x[i]<x[i-2]。但通过作图可以发现,x[i]的长短,还会略微影响x[i+1]的取值:

(a) 如果x[i]<x[i-2]-x[i-4]的话,接下来的x[i+1]只需要简单地满足小于x[i-1]即可(也就是它之前的对边),之后也是只要服从螺旋收缩的基本规则就行。

(b) 但是如果x[i]>=x[i-2]-x[i-4]的话,为了避免相交,x[i+1]不能超过x[i-1]-x[i-3]。这个等价于我们将x[i-1]-=x[i-3],之后从x[i+1]开始,只要仍服从螺旋收缩的基本规则即可。

特别注意,为了保证x[i-4]之类的操作不会下标越界,一个巧妙的方法是在x序列的前面添加四个零,模拟一圈螺旋膨胀的路径,然后从i=4开始考察它接下来的模式。

Leetcode Link