Sliding Window
TODO Write template for Sliding Window Average (reference)
Sliding Window Maximum
This implementation uses Monotonic Queue to compute a sliding window maximum of \(n\) elements in \(O(n)\). The operation add is amortized \(O(1)\), since each element enters once in the Deque.
from collections import deque class SlidingWindowMaximum: def __init__(self, size): self.size = size self.window = deque(maxlen=size) self.index = 0 def add(self, value): while len(self.window) > 0 and self.window[0][1] <= self.index - self.size: self.window.popleft() while len(self.window) > 0 and self.window[-1][0] <= value: self.window.pop() self.window.append((value, self.index)) self.index += 1 return self.max() def max(self): return self.window[0][0] w1 = SlidingWindowMaximum(3) assert w1.add(1) == 1 assert w1.add(2) == 2 assert w1.add(3) == 3 assert w1.add(2) == 3 assert w1.add(1) == 3 assert w1.add(1) == 2 assert w1.add(1) == 1 assert w1.add(9) == 9 assert w1.add(8) == 9 assert w1.add(7) == 9 assert w1.add(6) == 8 w2 = SlidingWindowMaximum(1) assert w2.add(9) == 9 assert w2.add(8) == 8