Самый длинный подотрезок с минимумом, равным X

1. Условие задачи

Дано: массив целых чисел nums и целое число x.

Нужно: найти длину самого длинного непустого непрерывного подотрезка, минимум на котором равен ровно x.

Если такого подотрезка нет, нужно вернуть -1.

Примеры:

nums = [3, 1, 4, 1, 5], x = 1
Ответ: 5

Подходит весь массив: его минимум равен 1.

nums = [1, 2, 0, 3, 1, 4], x = 1
Ответ: 3

Элемент 0 меньше x, поэтому через него нельзя провести подходящий подотрезок. Самый длинный вариант после него — [3, 1, 4].

nums = [2, 3, 4], x = 1
Ответ: -1

В массиве нет ни одного элемента, равного 1.

Ограничения:

• 1 <= len(nums) <= 10^5;
• значения массива и x могут быть отрицательными.

Ожидаемая сложность — O(N) времени и O(1) дополнительной памяти.

2. Решение

Решение в лоб

Можно перебрать начало подотрезка, а затем двигать его правую границу и поддерживать текущий минимум.

Так мы рассмотрим O(N²) подотрезков. Обновление минимума занимает O(1), поэтому итоговая сложность будет O(N²). Для массива длины до 10^5 это слишком медленно.

Переформулируем условие

Требование min(subarray) == x состоит из двух частей:

1. В подотрезке нет элементов меньше x.
2. В подотрезке есть хотя бы один элемент, равный x.

Элементы массива удобно разделить на три типа:

• num < x — запрещённый элемент, который разрывает текущий подотрезок;
• num == x — обязательный элемент, после которого минимум становится равен x;
• num > x — допустимый элемент, который удлиняет подотрезок, но сам по себе не гарантирует нужный минимум.

Каждый элемент меньше x делит массив на максимальные блоки, состоящие только из элементов >= x.

Если в таком блоке есть хотя бы один x, выгодно взять весь блок целиком. Его минимум равен x, а удаление элементов с краёв может только уменьшить длину.

Значит, задача сводится к поиску самого длинного блока из элементов >= x, внутри которого встретился x.

Решение без алгоритмических паттернов

Для этой задачи не обязательно знать скользящее окно или другие алгоритмические шаблоны. Достаточно базового навыка: считать длину текущей последовательности и сбрасывать счётчик, когда она прерывается.

Это почти 485. Max Consecutive Ones:

• элемент num >= x ведёт себя как единица — продолжает текущую последовательность;
• элемент num < x ведёт себя как ноль — сбрасывает её длину;
• небольшое усложнение: отдельно запоминаем, встретился ли внутри текущей последовательности элемент x.

Пока x не встретился, блок ещё нельзя использовать как ответ: его минимум больше x. Как только появился x, весь текущий блок становится подходящим, и дальше каждый элемент больше x только увеличивает его длину.

Алгоритм по шагам

1. В cur храним длину текущего блока из элементов >= x.
2. В has_x храним, встретился ли x в этом блоке.
3. Если очередной элемент меньше x, сбрасываем cur и has_x.
4. Иначе увеличиваем cur.
5. Если элемент равен x, устанавливаем has_x = True.
6. Обновляем ответ значением cur, только если текущий блок уже содержит x.
7. Если ни одного подходящего блока не было, возвращаем -1.

Визуализация на nums = [1, 2, 0, 3, 1, 4], x = 1

Ноль разрывает массив на два независимых блока: [1, 2] и [3, 1, 4]. Оба содержат x, но второй длиннее, поэтому ответ равен 3.

Код на Python

from typing import List


def longest_subarray_with_min(nums: List[int], x: int) -> int:
    answer = -1
    current_length = 0
    has_x = False

    for num in nums:
        if num < x:
            # Запрещённый элемент разрывает текущий блок
            current_length = 0
            has_x = False
        else:
            # Любой элемент >= x продолжает блок
            current_length += 1

            if num == x:
                has_x = True

            # Блок подходит, только если внутри уже встретился x
            if has_x:
                answer = max(answer, current_length)

    return answer

Почему алгоритм работает

Рассмотрим любой подходящий подотрезок. В нём не может быть элемента меньше x, иначе минимум был бы меньше x. Поэтому этот подотрезок целиком лежит внутри одного максимального блока из элементов >= x.

В подходящем подотрезке обязательно есть элемент x. Следовательно, весь максимальный блок, внутри которого лежит этот подотрезок, тоже содержит x, а значит, минимум всего блока равен x.

Максимальный блок не короче подотрезка внутри него. Поэтому достаточно сравнить длины всех максимальных блоков из элементов >= x, содержащих хотя бы один x. Именно это делает алгоритм.

Альтернатива: классическое скользящее окно

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

Будем поддерживать окно [left, right] и два счётчика:

• count_less — сколько в окне элементов меньше x;
• count_x — сколько в окне элементов, равных x.

После добавления нового элемента справа сжимаем окно слева, пока в нём есть запрещённый элемент меньше x. После этого все элементы окна не меньше x. Если при этом count_x > 0, минимум окна равен ровно x, и его длиной можно обновить ответ.

from typing import List


def longest_subarray_with_min(nums: List[int], x: int) -> int:
    answer = -1
    left = 0
    count_less = 0
    count_x = 0

    for right, num in enumerate(nums):
        if num < x:
            count_less += 1
        elif num == x:
            count_x += 1

        # Восстанавливаем условие: в окне не должно быть чисел < x
        while count_less > 0:
            if nums[left] < x:
                count_less -= 1
            elif nums[left] == x:
                count_x -= 1
            left += 1

        # Теперь все элементы >= x, а наличие x даёт минимум ровно x
        if count_x > 0:
            answer = max(answer, right - left + 1)

    return answer

Это полноценная реализация шаблона:

1. расширяем окно правой границей;
2. добавляем новый элемент в состояние окна;
3. сжимаем окно слева, пока оно не станет допустимым;
4. обновляем ответ.

Здесь шаблон немного избыточен: каждый элемент меньше x всё равно заставляет левую границу перескочить сразу за него. Поэтому счётчик текущего блока делает то же самое короче.

Но оба решения корректны. Первое подчёркивает, что задача решается навыками базового программирования и сводится к слегка усложнённой Max Consecutive Ones. Второе показывает, как тот же инвариант выражается через привычное скользящее окно.

Краевые случаи

• В массиве нет x. Даже если все элементы больше x, ответ остаётся равным -1.
• Все элементы меньше x. Каждый элемент разрывает текущий блок, поэтому подходящего подотрезка нет.
• Один элемент равен x. Ответ равен 1.
• Все элементы равны x. Подходит весь массив.
• Все элементы не меньше x, и хотя бы один равен x. Подходит весь массив.
• Несколько x в одном блоке. Они не разрывают блок, поэтому берём его целиком.
• Отрицательные числа. Знак значений не важен: алгоритм использует только сравнения с x.

3. Сложность алгоритмов

Счётчик текущего блока

Каждый элемент обрабатывается ровно один раз, а внутри цикла выполняется только константное число операций.

Итог по времени: O(N).

Используется несколько переменных, не зависящих от длины массива.

Итог по дополнительной памяти: O(1).

Скользящее окно

Правая граница проходит по массиву один раз. Левая граница тоже движется только вперёд и суммарно делает не больше N шагов, поэтому вложенный цикл не превращает решение в квадратичное.

Итог по времени: O(N).

Состояние окна хранится в нескольких переменных.

Итог по дополнительной памяти: O(1).

Вывод

Главный навык в этой задаче — разложить равенство минимума на два простых условия: все элементы подотрезка должны быть не меньше x, и хотя бы один из них должен быть равен x.

После этого задача превращается в немного усложнённую Max Consecutive Ones: считаем длину текущего блока, сбрасываем счётчик на элементе меньше x и дополнительно следим, встретился ли x.

Знать скользящее окно для такого решения необязательно. Но если этот паттерн уже хорошо освоен, использовать его тоже абсолютно нормально: он поддерживает тот же самый допустимый блок с помощью двух границ.

🐆