“скользящее окно максимум” Ответ

скользящее окно максимум

# Python program to find the maximum for
# each and every contiguous subarray of
# size k
 
from collections import deque
 
# A Deque (Double ended queue) based
# method for printing maximum element
# of all subarrays of size k
def printMax(arr, n, k):
     
    """ Create a Double Ended Queue, Qi that
    will store indexes of array elements.
    The queue will store indexes of useful
    elements in every window and it will
    maintain decreasing order of values from
    front to rear in Qi, i.e., arr[Qi.front[]]
    to arr[Qi.rear()] are sorted in decreasing
    order"""
    Qi = deque()
     
    # Process first k (or first window)
    # elements of array
    for i in range(k):
       
        # For every element, the previous
        # smaller elements are useless
        # so remove them from Qi
        while Qi and arr[i] >= arr[Qi[-1]] :
            Qi.pop()
         
        # Add new element at rear of queue
        Qi.append(i);
         
    # Process rest of the elements, i.e.
    # from arr[k] to arr[n-1]
    for i in range(k, n):
         
        # The element at the front of the
        # queue is the largest element of
        # previous window, so print it
        print(str(arr[Qi[0]]) + " ", end = "")
         
        # Remove the elements which are
        # out of this window
        while Qi and Qi[0] <= i-k:
             
            # remove from front of deque
            Qi.popleft()
         
        # Remove all elements smaller than
        # the currently being added element
        # (Remove useless elements)
        while Qi and arr[i] >= arr[Qi[-1]] :
            Qi.pop()
         
        # Add current element at the rear of Qi
        Qi.append(i)
     
    # Print the maximum element of last window
    print(str(arr[Qi[0]]))
     
# Driver code
if __name__=="__main__":
    arr = [12, 1, 78, 90, 57, 89, 56]
    k = 3
    printMax(arr, len(arr), k)
     
# This code is contributed by Shiv Shankar