Сложность: medium
У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.
Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени.
Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.
Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.
Пример:
Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).
👨💻 Алгоритм:
1⃣Инициализируйте переменную ans значением 0.
2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.
3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.
😎 Решение:
class Solution:
def getLastMoment(self, n: int, left: List[int], right: List[int]) -> int:
ans = 0
for num in left:
ans = max(ans, num)
for num in right:
ans = max(ans, n - num)
return ans
Ставь 👍 и забирай 📚 Базу знаний