sliding-window-maximum.md

Sliding Window Maximum

Jan 4, 2021 · 4 min read

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

Решение #

Решение «в лоб» — перебирать все числа в окне, находя максимум на каждом шаге снова.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const result = [];

  for (let i = k; i <= nums.length; i++) {
    // «вырезаем» окно и ищем максимум на каждом шаге
    result.push(Math.max(...nums.slice(i - k, i)));
  }
  return result;
};

Сложность — O(n * k). Если сдать это решение, то получим TLE.

Не зря эта задачка помечена как «hard» – брутфорс уже не прокатит.

Как всегда, на этом моменте нужно задать себе вопрос: «где совершается лишняя работа?». В примере выше ширина окна k равна 50000. С каждым шагом в окне меняется всего не более 2 чисел из 50000, а перечитываем мы все каждый раз! Давайте подумаем как можно быстее.

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

По-моему, есть два ключевых наблюдения, которые помогают прийти к решению с очередью:

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

Первое почти очевидно, а вот до второго нужно догадаться — понятнее становится если нарисовать.

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

Каждое число мы трогаем не более 2 раз (положить в очередь, удалить из очереди), поэтому итоговая сложность O(n). То есть вообще не важен размер окна!

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const q = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // удаляем невалидные индекс слева каждый раз,
    // когда окно двигается вправо
    if (q.length > 0 && q[0] < i - k + 1) {
      q.shift();
    }
    // удаляем невалидные индекс справа —
    // все, которые точно уже не станут максимумами,
    // по мере продвижения окна направо
    while (q.length > 0 && nums[q[q.length - 1]] < nums[i]) {
      q.pop();
    }
    // добавляем новый индекс в конец очереди
    q.push(i);
    // голова всегда показывает максимум
    if (i >= k - 1) {
      result.push(nums[q[0]]);
    }
  }
  return result;
};

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

Если нам не нужно ничего добавлять в начало, а только снимать, то есть очень простая реализация (правда, не оптимальная с точки зрения потребления памяти), которую я приведу ниже.

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

Сперва обновим код самого решения.

/**
  * @param {number[]} nums
  * @param {number} k
  * @return {number[]}
  */
var maxSlidingWindow = function(nums, k) {
- const q = [];
+ const q = new LinkedList();
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // удаляем невалидные индекс слева каждый раз
    // когда окно двигается вправо
-   if (q.length > 0 && q[0] < i - k + 1) {
+   if (q.length > 0 && q.front() < i - k + 1) {
      q.shift();
    }
    // удаляем невалидные индекс справа,
    // все которые точно уже не станут максимумами
    // по мере продвижения окна направо
-   while (q.length > 0 && nums[q[q.length - 1]] < nums[i]) {
+   while (q.length > 0 && nums[q.back()] < nums[i]) {
      q.pop();
    }
    // добавляем новый индекс в конец очереди
    q.push(i);
    // голова всегда показывает максимум
    if (i >= k - 1) {
-     result.push(nums[q[0]]);
+     result.push(nums[q.front());
    }
  }
  return result;
};

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

class LinkedList {
  constructor() {
    this.q = [];
    this.head = 0;
  }
  push(v) {
    this.q.push(v);
  }
  pop() {
    return this.q.pop();
  }
  shift() {
    this.q[this.head++];
  }
  front() {
    return this.q[this.head];
  }
  back() {
    return this.q[this.q.length - 1];
  }
  get length() {
    return this.q.length - this.head;
  }
}

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

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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