Build a Sliding-Window Metrics ToolkitStep 4 of 5

Monotonic deque: window maxima

12345

Step 4: Monotonic deque: window maxima

Dashboards often plot the peak value in each rolling window. Recomputing a max per window is O(n*k); a monotonic deque of indices gives O(n). The deque holds indices whose values are in decreasing order, so the front is always the current window maximum. Before appending an index, pop from the back while its value is less than or equal to the incoming value, and drop the front when it falls out of the window.

Implement max_window(nums, k) returning a list with the maximum of each contiguous window of size k. If k <= 0 or k > len(nums), return an empty list.

Example: max_window([1, 3, -1, -3, 5, 3, 6, 7], 3) is [3, 3, 5, 5, 6, 7].

Hints
Starter code
from collections import deque



def max_sum_window(nums, k):
    if k <= 0 or k > len(nums):
        return None
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        if window > best:
            best = window
    return best


def longest_unique(s):
    last = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        length = i - start + 1
        if length > best:
            best = length
    return best


def longest_at_most_k_distinct(s, k):
    if k <= 0:
        return 0
    counts = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        while len(counts) > k:
            left = s[start]
            counts[left] -= 1
            if counts[left] == 0:
                del counts[left]
            start += 1
        length = i - start + 1
        if length > best:
            best = length
    return best


def max_window(nums, k):
    # TODO: return a list of the maximum of each size-k window.
    # Use a deque of indices kept in decreasing value order (front = max).
    # Return [] when k <= 0 or k > len(nums).
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step