Три подхода к решению задачи максимума скользящего окна
В этом посте мы обсудим несколько решений проблемы максимального скользящего окна.
Если вы предпочитаете учиться с помощью видео, посмотрите следующее видео.
Постановка задачи
Вам дан массив целых чисел, есть скользящее окно размера 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
– это приоритетный ключ для сравнения- The
index
полезен для ограничения диапазона окна
Этапы выполнения:
- Сначала заполните
k
элементов в кучу - Добавить следующий элемент в кучу
- Удалить первый элемент из очереди, если его индекс находится вне диапазона окна
- Повторите шаги со 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 имеет три основные операции:
- Push: добавить элемент в очередь
- Pop: удалить элемент с любого конца очереди.
- 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
Если вам понравилась эта статья, пожалуйста, хлопните в ладоши, чтобы другие могли ее увидеть. 💚