Условие

Дан массив целых чисел arr. Верните true, если и только если он является "горным" массивом.

Массив называется "горным", если выполняются следующие условия:

• Длина массива составляет не менее 3 элементов.

• Существует индекс i (0 < i < arr.length - 1) такой, что:

• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Примеры

Input: arr = [2,1] Output: false

Input: arr = [3,5,5] Output: false

Input: arr = [0,3,2,1] Output: true

Решение

fun validMountainArray(arr: IntArray): Boolean {
    val n = arr.size
    if (n < 3) return false

    var i = 0

    // Подъем по возрастанию
    while (i + 1 < n && arr[i] < arr[i + 1]) {
        i++
    }

    // Пик не может быть первым или последним элементом
    if (i == 0 || i == n - 1) return false

    // Спуск по убыванию
    while (i + 1 < n && arr[i] > arr[i + 1]) {
        i++
    }

    // Если мы достигли конца массива, значит, это "горный" массив
    return i == n - 1
}

Временная сложность

O(n), где n — количество элементов в массиве, поскольку мы проходим по массиву один раз.

Пространственная сложность

O(1), так как используется постоянное количество дополнительной памяти.