"""
p95 — Sliding Window Maximum (LC 239)

INVARIANT (deque): the deque stores indices i_1 < i_2 < ... < i_m such that
  nums[i_1] > nums[i_2] > ... > nums[i_m]. Front index is the current window
  max. Each index is pushed once and popped at most once -> O(n) amortized.
"""
from __future__ import annotations

import heapq
import random
from collections import deque
from typing import List


def max_sliding_window_deque(nums: List[int], k: int) -> List[int]:
    """Monotonic decreasing deque of indices. O(n)."""
    if k == 0 or not nums:
        return []
    dq: deque[int] = deque()
    out: List[int] = []
    for i, v in enumerate(nums):
        # Pop smaller-or-equal values from the back; they can never be max again.
        while dq and nums[dq[-1]] <= v:
            dq.pop()
        dq.append(i)
        # Evict front if it has fallen out of the window.
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


def max_sliding_window_heap(nums: List[int], k: int) -> List[int]:
    """Max-heap with lazy deletion. O(n log n) worst case."""
    if k == 0 or not nums:
        return []
    heap: List[tuple[int, int]] = []  # (-val, idx)
    out: List[int] = []
    for i, v in enumerate(nums):
        heapq.heappush(heap, (-v, i))
        if i >= k - 1:
            while heap[0][1] <= i - k:
                heapq.heappop(heap)
            out.append(-heap[0][0])
    return out


def max_sliding_window_brute(nums: List[int], k: int) -> List[int]:
    """Oracle: O(n*k)."""
    if k == 0 or not nums:
        return []
    return [max(nums[i : i + k]) for i in range(len(nums) - k + 1)]


def edge_cases() -> None:
    nums = [1, 3, -1, -3, 5, 3, 6, 7]
    expected = [3, 3, 5, 5, 6, 7]
    assert max_sliding_window_deque(nums, 3) == expected
    assert max_sliding_window_heap(nums, 3) == expected

    # k == 1: each element is its own window.
    assert max_sliding_window_deque([1, 2, 3], 1) == [1, 2, 3]
    # k == n: single window.
    assert max_sliding_window_deque([4, 2, 7, 1], 4) == [7]
    # All equal.
    assert max_sliding_window_deque([5, 5, 5, 5], 2) == [5, 5, 5]
    # Decreasing.
    assert max_sliding_window_deque([9, 7, 5, 3, 1], 2) == [9, 7, 5, 3]
    # Increasing.
    assert max_sliding_window_deque([1, 2, 3, 4, 5], 3) == [3, 4, 5]
    # Negative numbers.
    assert max_sliding_window_deque([-5, -3, -8, -1], 2) == [-3, -3, -1]


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(1, 10)
        nums = [rng.randint(-10, 10) for _ in range(n)]
        k = rng.randint(1, n)
        d = max_sliding_window_deque(nums, k)
        h = max_sliding_window_heap(nums, k)
        b = max_sliding_window_brute(nums, k)
        assert d == b, (nums, k, d, b)
        assert h == b, (nums, k, h, b)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")