Наименьший стабильный индекс II

Постановка задачи

max(nums[0..i]) - min(nums[i..n - 1])

nums = [5, 0, 1, 4], k = 3

3

nums = [3, 2, 1], k = 1

-1

nums = [0], k = 0

0

Решение

Наивное решение - для каждого индекса заново искать максимум слева и минимум справа. Для одного индекса это O(n), для всех индексов получится O(n²).

На ограничении 10⁵ такой подход не подойдет. Нам нужно один раз подготовить информацию, которая позволит быстро проверить любой индекс.

Эта задача хорошо ложится на идею префиксных сумм в более общем виде: заранее считаем значение для каждого префикса или суффикса, а потом используем его за O(1).

Тут нам нужна не сумма, а два агрегата:

• префиксный максимум: max(nums[0..i])
• суффиксный минимум: min(nums[i..n - 1])

Идея решения:

Суффиксный минимум для каждого индекса можно посчитать заранее. Создадим массив right, где:

right[i] = min(nums[i..n - 1])

Его удобно строить справа налево:

right[n - 1] = nums[n - 1]
right[i] = min(nums[i], right[i + 1])

После этого идем слева направо и поддерживаем переменную left:

left = max(nums[0..i])

На каждом индексе i значение нестабильности равно:

left - right[i]

Если оно не больше k, сразу возвращаем i, потому что мы идем слева направо и ищем самый маленький подходящий индекс.

Почему достаточно одного прохода после подготовки right?

Для индекса i нам нужны только две величины:

1. Лучшее значение слева, то есть максимум на префиксе.
2. Лучшее значение справа, то есть минимум на суффиксе.

Суффиксный минимум мы уже знаем из массива right. Для префиксного максимума не нужен отдельный массив, потому что при движении слева направо он обновляется одной операцией:

left = max(left, nums[i])

Основные шаги:

1. Создаем массив right длины n.
2. Заполняем right[n - 1] = nums[n - 1].
3. Идем справа налево и считаем суффиксные минимумы.
4. Идем слева направо:
   • обновляем left, максимум на текущем префиксе
   • считаем left - right[i]
   • если значение не больше k, возвращаем i
5. Если подходящего индекса нет, возвращаем -1.

Рассмотрим пример:

nums = [5, 0, 1, 4], k = 3

Сначала построим right:

1. right[3] = 4
2. right[2] = min(1, 4) = 1
3. right[1] = min(0, 1) = 0
4. right[0] = min(5, 0) = 0

Получаем:

right = [0, 0, 1, 4]

Теперь идем слева направо:

1. Индекс 0, число 5.

   • left = 5
   • right[0] = 0
   • нестабильность 5 - 0 = 5
   • 5 > 3, индекс не подходит

2. Индекс 1, число 0.

   • left = max(5, 0) = 5
   • right[1] = 0
   • нестабильность 5 - 0 = 5
   • 5 > 3, индекс не подходит

3. Индекс 2, число 1.

   • left = max(5, 1) = 5
   • right[2] = 1
   • нестабильность 5 - 1 = 4
   • 4 > 3, индекс не подходит

4. Индекс 3, число 4.

   • left = max(5, 4) = 5
   • right[3] = 4
   • нестабильность 5 - 4 = 1
   • 1 <= 3, возвращаем 3

Оценка сложности

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

Мы один раз идем справа налево, чтобы построить массив суффиксных минимумов, и один раз идем слева направо, чтобы найти первый стабильный индекс.

Итоговая временная сложность: O(n).

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

Мы храним массив right длины n.

Итоговая пространственная сложность: O(n).

Код решения

Приведем код решения.

func firstStableIndex(nums []int, k int) int {
    n := len(nums)
    right := make([]int, n)
    right[n-1] = nums[n-1]
    for i := n - 2; i >= 0; i-- {
        right[i] = min(nums[i], right[i+1])
    }
 
    left := 0
    for i, x := range nums {
        left = max(left, x)
        if left-right[i] <= k {
            return i
        }
    }
    return -1
}

Итоги

Эта задача показывает, что паттерн префиксных сумм шире, чем просто суммы подмассивов. Иногда нам нужно заранее посчитать другой агрегат на префиксе или суффиксе.

1. Главная идея: заранее считаем right[i], минимальный элемент на суффиксе от i до конца массива.

2. Проверка индекса: во время прохода слева направо поддерживаем left, максимальный элемент на префиксе, и проверяем left - right[i] <= k.

3. Почему возвращаем сразу: мы идем по индексам в порядке возрастания, поэтому первый подходящий индекс и будет ответом.

4. Сложность: два линейных прохода дают O(n) по времени и O(n) по памяти.