Метод скользящего окна

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

• знания в области алгоритмов делают код более производительным — просто на автомате думаешь о том, какая сложность у твоего решения и выбираешь оптимальный вариант
• в топовые компании без умения решать задачки на алгоритмы не попасть

Так что придётся учить.

К сожалению, всё задачи в мире не прорешаешь, и не факт что на собесе попадётся одна из сотен порешённых задач, а стоит завалить одну и всё, отказ. Но есть лайфхак по решению алгоритмических задач. Им является не просто прорешивание всего подряд, а знание определённых подходов к решению семейства задач. А уж эти подходы можно пересчитать на пальцах и они закроют процентов 90 возможных задач.

Сегодня поговорим о методе скользящего окна и посмотрим его применение на конкретной задаче. Он должен сразу всплыть в голове, если в задачке просят найти самую длинную/короткую строку, подмассив или какое-то значение на их основе.

Задача

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

Аргументы: [1, 12, -5, -6, 50, 3], k = 4
Ответ: 12.75
Объяснение: Максимальное среднее — это (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

(если что, это задачка с литкода)

Брутфорсим

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

function findMaxAverage(nums: number[], k: number): number {
  let maxAverage = Number.MIN_VALUE

  for (let i = 0; i < nums.length - k + 1; i++) {
    let sum = 0 // сумма следующих k элементов

    for (let j = i; j < i + k; j++) {
      sum += nums[j]
    }

    const average = sum / k

    maxAverage = Math.max(maxAverage, average)
  }

  return maxAverage
}

console.assert(findMaxAverage([1, 12, -5, -6, 50, 3], 4) === 12.75)

Сложность этого решения O(n*k), где n - длина переданного массива. Но это наивное решение редко удовлетворит собеседующего, литкод тоже на это намекает, он пожалуется, что превышен лимит по времени. Так что давайте подумаем, как найти решение получше.

Если внимательно взглянуть на текущее решение, то легко заметить, что при каждом сдвиге мы заново высчитываем сумму элементов. Можно ли как-нибудь переиспользовать сумму для пересекающихся подмассивов?

Скользим

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

function findMaxAverage(nums: number[], k: number): number {
  // считаем сумму первого окна
  let sum = 0
  for (let i = 0; i < k; i++) {
    sum += nums[i]
  }

  let res = sum // храним максимальную сумму

  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k] // добавляем вошедший/убираем ушедший
    res = Math.max(res, sum)
  }

  return res / k
}

console.assert(findMaxAverage([1, 12, -5, -6, 50, 3], 4) === 12.75)

Временная сложность - O(n), сложность по памяти - O(1). Идеально.

Можно ещё похвастаться:

Когда использовать метод скользящего окна?

• в задаче передаётся упорядоченная и итерируемая структура данных, вроде массива или строки
• просят найти подпоследовательность в массиве/строке, самое длинное/короткое, среднее/большое/маленькое и т. д.
• первым в голову приходит наивное решение со сложностью $O(n^2)$ или даже $O(2^n)$

Метод скользящего окна позволяет улучшить вычислительную сложность до линейной, а по памяти — до константной. И это классно.