LeetCode 筆記 - 1503. Last Moment Before All Ants Fall Out of a Plank

解析饒富趣味的螞蟻落木板問題。雖然題目描述螞蟻相遇會交換方向,本文揭露解題關鍵:可將相遇視為螞蟻直接「穿過」彼此。透過此簡化思維,只需找出距離邊緣最遠的螞蟻掉落時間,即可秒解這個看似複雜的運動邏輯題。

發佈
閱讀
約 1 分鐘
字數
211

題目在此 1503. Last Moment Before All Ants Fall Out of a Plank

在一個木板上隨機擺放一些往左或往右的螞蟻,請問最後一隻螞蟻掉下去的時間點是多少?

當不同方向的螞蟻相遇時,會互相交換方向並繼續走。

解題思維

其實可以當作他們不會交換方向,因為交換方向的結果是一樣的。
所以我們只要找出最大的時間點即可。image 106

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
result = 0

max_left = 0
for l in left:
max_left = max(max_left, l)

min_right = n
for r in right:
min_right = min(min_right, r)

result = max(max_left, n - min_right)

return result
image 106

也許你也會想看看

輸入關鍵字開始搜尋 · ↑↓ 選擇 · Enter 開啟