mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
024e90d731
* add monotonic queue algorithm * add monotonic queue algorithm * add monotonic queue algorithm * monotonic queue * updating DIRECTORY.md * Rename file to correct directory structure * updating DIRECTORY.md --------- Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: cclauss <cclauss@users.noreply.github.com>
40 lines
1.2 KiB
Python
40 lines
1.2 KiB
Python
from __future__ import annotations
|
|
|
|
from collections import deque
|
|
|
|
arr = [1, 3, -1, -3, 5, 3, 6, 7]
|
|
window_size = 3
|
|
expect = [3, 3, 5, 5, 6, 7]
|
|
|
|
|
|
def max_sliding_window(arr: list[float], window_size: int) -> list[float]:
|
|
"""
|
|
Given an array of integers nums, there is a sliding window of size k which is moving
|
|
from the very left of the array to the very right.
|
|
Each time the sliding window of length window_size moves right by one position.
|
|
Return the max sliding window.
|
|
>>> max_sliding_window(arr, window_size) == expect
|
|
True
|
|
"""
|
|
max_val = []
|
|
mono_queue: deque = deque()
|
|
for i in range(len(arr)):
|
|
# pop the element if the index is outside the window size k
|
|
if mono_queue and i - mono_queue[0] >= window_size:
|
|
mono_queue.popleft()
|
|
# keep the queue monotonically decreasing
|
|
# so that the max value is always on the top
|
|
while mono_queue and arr[i] >= arr[mono_queue[-1]]:
|
|
mono_queue.pop()
|
|
mono_queue.append(i)
|
|
# the maximum value is the first element in queue
|
|
if i >= window_size - 1:
|
|
max_val.append(arr[mono_queue[0]])
|
|
return max_val
|
|
|
|
|
|
if __name__ == "__main__":
|
|
from doctest import testmod
|
|
|
|
testmod()
|