Problem#
木棍長 n 個單位，上頭有一群螞蟻在走，各自朝著左方與右方，每秒移動一個單位。每當螞蟻相遇時，會各自往反方向走。當螞蟻走出 0 或 n 時會掉出去，給你朝左與朝右的螞蟻初始位置，問你經過幾秒後，所有螞蟻都掉出木棍?
測資限制#
- $1 \le n \le 10^4$
想法#
Naive: 直接模擬每個螞蟻的走路情況 $O(n^2)$。
但可以發現是即使螞蟻相撞，改變方向，也可以看做兩隻螞蟻維持各自的方向繼續走(雖然此時螞蟻已經是不同隻，但我們並不在乎)，所以對於所有往左的螞蟻，最長距離就是 max(left[i]-0)；對於所有往右的螞蟻，最長距離是 max(n-right[i])，找出最大的數字就是答案。 $O(n)$
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$