Como declarar e manter o máximo ao deslocar a janela?

Para manter o máximo numa janela ao deslocar a janela, muitas vezes usa-se uma estrutura de dados: uma fila dupla (deque). A ideia é armazenar os índices dos elementos em ordem decrescente de valores, de modo que:

• Ao adicionar um novo elemento, removemos do final da fila todos os elementos menores que o novo, pois eles não podem ser o máximo.
• Ao deslocar a janela, removemos do início da fila os elementos que saíram do limite da janela.

Isso permite obter o máximo na janela atual em O(1), e processar todo o array em O(n).

Exemplo em Python:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()  # armazena índices
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if dq[0] == i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Exemplo de uso
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))  # [3,3,5,5,6,7]