Premium

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

Подмассив с частотой не больше k

Найти длину самого длинного подмассива, где каждый элемент встречается не более k раз

Средний

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

Описание (LeetCode - 2958. Length of Longest Subarray With At Most K Frequency)

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

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

Пример 1:

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

Результат:

6

Пояснение:

Самый длинный подходящий подмассив - [1, 2, 3, 1, 2, 3]. Каждое число встречается в нем ровно два раза.

Пример 2:

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

Результат:

2

Пояснение:

Каждый элемент может встретиться не более одного раза, поэтому максимальная длина равна 2 (например, для подмассива [1, 2]).

Пример 3:

nums = [5, 5, 5, 5, 5, 5, 5, 5], k = 3

Результат:

3

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

  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁹
  • 1 <= k <= nums.length

Решение

Наивное решение перебирает все возможные подмассивы и для каждого считает частоты элементов. Это требует времени O(n²) или O(n³).

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

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

Поддерживаем окно [left..right] и хеш-таблицу freq, где храним частоту каждого элемента в текущем окне.

Мы последовательно расширяем окно вправо, добавляя nums[right]. Поскольку до этого момента все элементы встречались не более k раз, после добавления нового числа превысить лимит может только nums[right]. Если freq[nums[right]] > k, мы сдвигаем left вправо и уменьшаем счетчики уходящих элементов до тех пор, пока частота nums[right] снова не станет равной k.

На каждом шаге обновляем максимальную длину окна maxLen.

Динамическое окно и частоты

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

  1. Инициализируем хеш-таблицу freq, указатель left = 0 и переменную maxLen = 0.
  2. Проходим указателем right по массиву от 0 до конца.
  3. Увеличиваем счетчик текущего элемента: freq[nums[right]].
  4. Пока freq[nums[right]] > k:
    • уменьшаем freq[nums[left]];
    • увеличиваем left.
  5. Обновляем максимальную длину: maxLen = max(maxLen, right - left + 1).
  6. Возвращаем maxLen.

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

nums = [1, 2, 3, 1, 2, 3, 1, 2], k = 2
  1. right = 2: окно [1, 2, 3], все частоты равны 1. maxLen = 3.
right = 2
  1. right = 5: окно [1, 2, 3, 1, 2, 3], каждая частота равна 2. maxLen = 6.
right = 5, maxLen = 6
  1. right = 6: добавляем третью единицу, freq[1] = 3 > k. Условие нарушено.
freq[1] = 3 > k
  1. Сдвигаем left вправо на 1 и убираем nums[0]. Окно снова корректно, длина остается 6.
left = 1

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

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

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

Указатель right проходит по массиву один раз, а указатель left только сдвигается вправо и также проходит по массиву не более одного раза. Каждое число добавляется в хеш-таблицу и удаляется из нее за O(1).

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

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

Хеш-таблица хранит частоты уникальных элементов внутри текущего окна. В худшем случае в окно попадут все n различных чисел.

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

Код решения

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

func maxSubarrayLength(nums []int, k int) int {
    freq := make(map[int]int)
    left := 0
    maxLen := 0
 
    for right := 0; right < len(nums); right++ {
        freq[nums[right]]++
        for freq[nums[right]] > k {
            freq[nums[left]]--
            left++
        }
        maxLen = max(maxLen, right - left + 1)
    }
 
    return maxLen
 
}

Итоги

Задача Length of Longest Subarray With At Most K Frequency - наглядный пример использования динамического скользящего окна с подсчетом частот.

  1. Суть алгоритма: расширяем окно вправо и ведем подсчет частот в хеш-таблице. Если частота текущего элемента превышает k, сдвигаем left, пока окно снова не станет допустимым.
  2. Эффективность:
    • Временная сложность: O(n), так как каждый элемент входит в окно и выходит из него не более одного раза.
    • Пространственная сложность: O(n) для хранения частот в хеш-таблице.
  3. Граничные случаи:
    • k = 1: все элементы в окне должны быть уникальными (длина самого длинного подмассива без повторений).
    • Все элементы одинаковые: ответ равен min(k, n).
  4. Оптимальное решение: одно динамическое окно с хеш-таблицей находит максимальный подмассив за один линейный проход.
Войдите чтобы отмечать прогресс