Три подхода к решению задачи максимума скользящего окна

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

Если вы предпочитаете учиться с помощью видео, посмотрите следующее видео.

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

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

Возвращает максимальное скользящее окно.

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Решение 1: грубая сила

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

Время: O(Nk)
Пространство: O(1) без учета выходного массива

Решение Brute force почти не использует дополнительное пространство. Но это наименее эффективный алгоритм.

def simple(nums, k):
   res = []
   length = len(nums)
        
   i = 0
   while i < length-k+1:
     mx = max(nums[i:i+k])
     res.append(mx)
     i +=1
                
     return res

Решение 2. Приоритетная очередь

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

Мы храним item = (value, index) пару внутри приоритетной очереди.

  • value – это приоритетный ключ для сравнения
  • Theindex полезен для ограничения диапазона окна

Этапы выполнения:

  1. Сначала заполните k элементов в кучу
  2. Добавить следующий элемент в кучу
  3. Удалить первый элемент из очереди, если его индекс находится вне диапазона окна
  4. Повторите шаги со 2 по 3

Вот код:

import heapq
class Solution:
    def maxSlidingWindow(self, nums, k):
        lens = len(nums)
        h  = []
        res = []
        
        for r in range(k):
            heapq.heappush(h, (-nums[r],r))
        res.append(-h[0][0])
        
        
        for r in range(k, lens):
            l = r-k+1
            # window index range: l, l+1, ..., l+k-1
            heapq.heappush(h, (-nums[r],r))
            while h[0][1] <l or h[0][1] > l+k-1:
                heapq.heappop(h)
            res.append(-h[0][0])
        
        return res

Решение 3: Монотонный дек

Очереди — это обобщение стеков и очередей (название произносится как «колода» и является сокращением от «двусторонняя очередь»).

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

Monotonic deque имеет три основные операции:

  1. Push: добавить элемент в очередь
  2. Pop: удалить элемент с любого конца очереди.
  3. max: просмотреть максимальный элемент в O(1)

Вот код

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums, k):
        res = []
        
        d = deque([])
        
        for r in range(len(nums)): 
            # remove item outside the window
            #  1. if first index in  Q(Deque) < i-k+1
            if d and d[0][1] < r-k+1:
                d.popleft()
            
            #  2. a new bigger item comes
            while d and nums[r] >= d[0][0]:
                d.popleft()
            
            # keep Monotonic
            while d and nums[r] > d[-1][0]:
                d.pop()
                
            d.append((nums[r],r))
            if r >= k-1:
                res.append(d[0][0])
        
        return res

Если вам понравилась эта статья, пожалуйста, хлопните в ладоши, чтобы другие могли ее увидеть. 💚