求繩子能夠覆蓋的最多點數
作者：由 硬體工程師 發表于 遊戲時間：2021-04-15
問題描述
輸入：
一根繩子的長度
l
一個數組，陣列中包含了一堆座標點
輸出：
用繩子覆蓋座標點，最多能覆蓋的點數
思路
可以使用雙指標來做，前一個指標用
i
表示，後一個指標用
front
表示。如果兩個指標間的長度小於
l
，那麼就檢查
i
和
front + 1
之間的長度和
l
的關係。如果長度比
l
要小的話，那麼
front
就加
1
。 反之，
i+1
。
複雜度：O（n）
程式碼
def
maxCovered
（
positions
，
l
）：
if
len
（
positions
）
<=
0
：
return
0
if
l
<=
0
：
return
0
front
=
0
result
=
0
for
i
in
range
（
1
，
len
（
positions
）
-
1
）：
while
（
front
+
1
）
<
len
（
positions
）：
if
（
positions
［
front
+
1
］
-
positions
［
i
］）
<=
l
：
front
=
front
+
1
else
：
break
if
（
front
-
i
+
1
）
>
result
：
result
=
front
-
i
+
1
return
result
（
maxCovered
（［
1
，
3
，
7
，
8
，
9
，
11
］，
4
））
