1732. Find the Highest Altitude

LeetCode задача 1732

Задача

Велосипедист совершает путешествие, которое состоит из n + 1 точек на разных высотах. Путешествие начинается с точки 0, где высота равна 0.

Дан целочисленный массив gain длиной n, где gain[i] — это прирост высоты между точками i и i + 1 для всех (0 <= i < n).

Задача - вернуть самую высокую высоту точки.

Подход

В этой задаче, вам нужно пройти по массиву gain и вычислить текущую высоту на каждом этапе. При этом следует отслеживать самую высокую высоту, которую вы достигли.

1. Прирост высоты между точками - это то, сколько велосипедист фактически проехал. Эти данные нам известны.
2. Необходимо узнать, где велосипедист оказался после шага 1.
   1. Чтобы узнать это - мы можем текущую к текущей позиции, где он сейчас, прибавить “прирост”.
   2. Тогда получаем, что из позиции 0 и прироста -5, велосипедист окажется в новой точке -5 (0 + (-5))
   3. С новой позиции -5 и прироста 1, окажется в точке -4 (-5 + 1) и т.д.
3. Остается посчитать и вернуть самую высокую позицию, в которой был велосипедист.

Алгоритм

1. Инициализируем текущую высоту (current_altitude) как 0 и максимальную высоту (max_altitude) как 0.
2. Проходим через каждый элемент массива gain, увеличивая current_altitude на значение этого элемента.
3. Сравниваем current_altitude с max_altitude. Если current_altitude больше, то устанавливаем max_altitude равным current_altitude.
4. Возвращаем max_altitude как ответ.

Решение

def largestAltitude(gain):
    current_altitude = 0  # текущая высота
    max_altitude = 0  # максимальная высота
    
    for i in gain:
        current_altitude += i
        max_altitude = max(max_altitude, current_altitude)
    
    return max_altitude