Сложность: medium
Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.
Пример:
Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
👨💻 Алгоритм:
1⃣Инициализируйте переменные для отслеживания текущего основания и максимальной длины горного массива.
2⃣Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива.
3⃣Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.
😎 Решение:
class Solution:
def longestMountain(self, arr: List[int]) -> int:
n = len(arr)
ans = 0
base = 0
while base < n:
end = base
if end + 1 < n and arr[end] < arr[end + 1]:
while end + 1 < n and arr[end] < arr[end + 1]:
end += 1
if end + 1 < n and arr[end] > arr[end + 1]:
while end + 1 < n and arr[end] > arr[end + 1]:
end += 1
ans = max(ans, end - base + 1)
base = max(end, base + 1)
return ans
Ставь 👍 и забирай 📚 Базу знаний