Maximum dans une fenêtre glissante avec une deque monotone

Problème du maximum d'une fenêtre glissante

from collections import deque

# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute:   ', sliding_max_brute(nums, k))

File monotone à double extrémité : idée clé

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()  # stores indices; values are decreasing
    result = []

    for i, n in enumerate(nums):
        # 1. Remove indices outside the current window
        while dq and dq[0] <= i - k:
            dq.popleft()

        # 2. Remove indices with smaller values from the back
        while dq and nums[dq[-1]] <= n:
            dq.pop()

        dq.append(i)

        # 3. Record max when first full window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])   # front = max of current window

    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3))  # [3, 3, 5, 5, 6, 7]

Suivi de la file à double extrémité étape par étape

from collections import deque

def sliding_window_max_trace(nums, k):
    dq = deque()
    result = []
    for i, n in enumerate(nums):
        while dq and dq[0] <= i - k:
            print(f'  Remove expired index {dq[0]} from front')
            dq.popleft()
        while dq and nums[dq[-1]] <= n:
            print(f'  Remove smaller index {dq[-1]} (val={nums[dq[-1]]}) from back')
            dq.pop()
        dq.append(i)
        print(f'i={i} n={n}: dq={list(dq)} vals={[nums[j] for j in dq]}')
        if i >= k - 1:
            win_max = nums[dq[0]]
            result.append(win_max)
            print(f'  Window {nums[max(0,i-k+1):i+1]} -> max={win_max}')
    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
result = sliding_window_max_trace(nums, 3)
print('Result:', result)

Pourquoi chaque élément est ajouté et retiré au plus une fois

from collections import deque

def sliding_window_max_instrumented(nums, k):
    dq = deque()
    result = []
    front_pops = back_pops = pushes = 0

    for i, n in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft(); front_pops += 1
        while dq and nums[dq[-1]] <= n:
            dq.pop(); back_pops += 1
        dq.append(i); pushes += 1
        if i >= k - 1:
            result.append(nums[dq[0]])

    print(f'n={len(nums)}: pushes={pushes}, front_pops={front_pops}, back_pops={back_pops}')
    print(f'Total deque ops = {pushes + front_pops + back_pops} <= 3n = {3*len(nums)}')
    return result

import random; random.seed(0)
nums = [random.randint(-100, 100) for _ in range(20)]
sliding_window_max_instrumented(nums, 5)

Minimum d'une fenêtre glissante

from collections import deque

def sliding_window_min(nums, k):
    dq = deque()  # increasing monotonic deque
    result = []

    for i, n in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()               # expired
        while dq and nums[dq[-1]] >= n:
            dq.pop()                   # pop larger values from back
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])  # front = min
    return result

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print('Max k=3:', sliding_window_min.__name__, '->', end=' ')
print(sliding_window_min(nums, 3))   # [-1, -3, -3, -3, 3, 3]

from collections import deque
def sliding_window_max(nums, k):
    dq = deque(); result = []
    for i, n in enumerate(nums):
        while dq and dq[0] <= i-k: dq.popleft()
        while dq and nums[dq[-1]] <= n: dq.pop()
        dq.append(i)
        if i >= k-1: result.append(nums[dq[0]])
    return result

print('Max k=3:', sliding_window_max(nums, 3))   # [3,3,5,5,6,7]

Problème des sauts VI : DP avec une file monotone à double extrémité

from collections import deque

def max_result(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])   # indices of max dp values in current window

    for i in range(1, n):
        # Remove expired indices
        while dq and dq[0] < i - k:
            dq.popleft()
        # dp[i] = nums[i] + max dp in window [i-k, i-1]
        dp[i] = nums[i] + dp[dq[0]]
        # Maintain decreasing deque on dp values
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)

    return dp[n - 1]

print(max_result([1,-1,-2,4,-7,3], 2))    # 7: path 1->4->3
print(max_result([10,-5,-2,4,0,3], 3))    # 17: path 10->4->3
print(max_result([1,-5,-20,4,-1,3,-6,-3], 2))  # 0

Maximum d'une fenêtre glissante : alternative avec un arbre de segments

# Sparse table for static RMQ (range maximum query)
import math

def build_sparse_table(arr):
    n = len(arr)
    LOG = int(math.log2(n)) + 1 if n else 1
    table = [[0]*n for _ in range(LOG)]
    table[0] = arr[:]
    j = 1
    while (1 << j) <= n:
        for i in range(n - (1 << j) + 1):
            table[j][i] = max(table[j-1][i], table[j-1][i + (1 << (j-1))])
        j += 1
    return table

def query(table, l, r):
    k = int(math.log2(r - l + 1))
    return max(table[k][l], table[k][r - (1 << k) + 1])

arr = [1, 3, -1, -3, 5, 3, 6, 7]
table = build_sparse_table(arr)
k = 3
result = [query(table, i, i + k - 1) for i in range(len(arr) - k + 1)]
print('Sparse table result:', result)  # [3, 3, 5, 5, 6, 7]

Plus long sous-tableau de 1 après suppression d'un élément

def longest_subarray(nums):
    left = 0
    zeros = 0
    max_len = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > 1:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        # Window [left, right] has at most 1 zero
        # After deleting one element, length = right - left (not +1, since we delete one)
        max_len = max(max_len, right - left)

    return max_len

print(longest_subarray([1,1,0,1]))       # 3: delete the 0
print(longest_subarray([0,1,1,1,0,1,1,0,1]))  # 5
print(longest_subarray([1,1,1]))          # 2: must delete one 1

Comparaison entre file à double extrémité, file et pile

from collections import deque

# deque as stack
stack = deque()
stack.append(1); stack.append(2); stack.append(3)
print('Stack pop:', stack.pop())  # 3 (LIFO)

# deque as queue
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print('Queue pop:', queue.popleft())  # 1 (FIFO)

# deque as sliding window with front expiry + back monotonic
dq = deque()
nums = [3, 1, 4, 1, 5, 9, 2, 6]
k = 3
for i, n in enumerate(nums):
    while dq and dq[0] <= i - k: dq.popleft()   # expire front
    while dq and nums[dq[-1]] <= n: dq.pop()     # maintain back
    dq.append(i)
    if i >= k - 1:
        print(f'Window {nums[max(0,i-k+1):i+1]}: max={nums[dq[0]]}')

Plus court sous-tableau dont la somme est au moins K : file à double extrémité + sommes préfixes

from collections import deque

def shortest_subarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    dq = deque()    # monotonic increasing deque of indices into prefix
    result = float('inf')

    for right in range(n + 1):
        # Pop from front: valid subarrays ending at `right`
        while dq and prefix[right] - prefix[dq[0]] >= k:
            result = min(result, right - dq.popleft())
        # Pop from back: maintain increasing deque
        while dq and prefix[dq[-1]] >= prefix[right]:
            dq.pop()
        dq.append(right)

    return result if result != float('inf') else -1

print(shortest_subarray([1], 1))               # 1
print(shortest_subarray([1, 2], 4))            # -1
print(shortest_subarray([2, -1, 2], 3))        # 3
print(shortest_subarray([84,-37,32,40,95], 167))  # 3

Stratégie d'entretien pour les problèmes de files à double extrémité

from collections import deque

# Clean, interview-ready template
def sliding_window_max_template(nums, k):
    if not nums or k == 0:
        return []

    dq = deque()   # monotonic decreasing, stores indices
    result = []

    for i in range(len(nums)):
        # Invariant 1: remove expired indices (outside window)
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Invariant 2: remove indices with smaller values (useless)
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Record result once first full window is established
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Complexity: O(n) time, O(k) space
print(sliding_window_max_template([1,3,-1,-3,5,3,6,7], 3))
print(sliding_window_max_template([1], 1))
print(sliding_window_max_template([], 3))

Vérification rapide

Récapitulatif de la leçon