py_sliding_window_maximum

Código comentado línea a línea y paso a paso:

Python · paso a paso

Entregas: py_sliding_window_maximum.py con sliding_window_maximum(nums, k). Rank 04 · nivel 4.

Qué pide (en palabras normales)

Máximo de cada ventana de k elementos consecutivos. [1,3,-1,-3,5,3,6,7], 3 → [3,3,5,5,6,7].
k <= 0, k mayor que la lista, o lista vacía → [].

Subject (enunciado original)

Write a function that finds the maximum element in each sliding window of size k in an array. Return a list of maximums for each window position.

The function should:
- Slide a window of size k through the array
- Find the maximum element in each window position
- Return a list of maximum values
- Handle edge cases (empty array, k <= 0, k > array length)
- Return empty list for invalid inputs

Expected file: py_sliding_window_maximum.py
Function signature:
def sliding_window_maximum(nums: list[int], k: int) -> list[int]:

Examples:
sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3)
=> [3, 3, 5, 5, 6, 7]
sliding_window_maximum([1, 2, 3, 4, 5], 2)
=> [2, 3, 4, 5]
sliding_window_maximum([5, 4, 3, 2, 1], 1)
=> [5, 4, 3, 2, 1]
sliding_window_maximum([1, 2, 3], 3)
=> [3]
sliding_window_maximum([1, 2, 3], 4)
=> []
sliding_window_maximum([], 2)
=> []
sliding_window_maximum([1, 2, 3], 0)
=> []

La versión fácil

return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

Correcta y una línea, pero O(n·k). Con n = 100000 y k = 50000 son 2.5 mil millones de comparaciones: timeout seguro. Es nivel 4 por algo.

La versión O(n): cola monótona

Mantengo una lista de índices candidatos cuyo valor va decreciendo. Cuando entra un número, todo lo que haya en la cola menor o igual que él ya no puede ser máximo de ninguna ventana futura (él es mayor y además sale más tarde). Los expulso por la cola. La cabeza es siempre el máximo de la ventana actual; cuando su índice se sale de la ventana, avanzo.

for i, value in enumerate(nums):
    while len(candidates) > head and nums[candidates[-1]] <= value:
        candidates.pop()
    candidates.append(i)
    if candidates[head] <= i - k:
        head += 1
    if i >= k - 1:
        result.append(nums[candidates[head]])

Cada índice entra y sale una vez: lineal.

Sin `deque`

Lo normal es collections.deque y popleft(), pero el import suspende. Sustituto: una lista normal y un entero head que apunta a la cabeza lógica. "Sacar por delante" es head += 1. Los elementos viejos se quedan en la lista, pero nunca se miran.

Trampas