Python Solution


  • 0
    G

    Maintain a double ended queue which store the greatest elements to the right in the current window.
    For example:
    window - [4 2 3 1] will have a queue - [4 3 1]
    window - [4 3 3 1] will have a queue - [4 3 3 1]
    window - [2 4 5 3] will have a queue - [5 3]

    The max element of the window will be the first element of the queue.

    when we move the window to the right by one element:

    1. if the max element in the queue is equal to the element removed from the window, then the max element is removed from the queue.
    2. the new element added to the window is compared to all the elements in the queue from the right and smaller elements are removed.
      For example:
      queue - [4 3 1] and new element is 2 the new queue is [4 3 2]
      queue - [4 3 1] and new element is 5 the new queue is [5]
            dq = []                // double ended queue
            n = len(A)          // size of the array given
            ma = -float('inf')  
            for l in range(B):  // create the initial double ended queue
                if A[B-1-l]>=ma:
                    ma = A[B-1-l]
                    dq.append(ma)
            dq.reverse()
    
            a = []
            a.append(dq[0])
            for i in range(B,n): // window is moved one step at a time 
                if A[i-B]==dq[0]: // step 1 from the above explanation
                    dq = dq[1:]
                p = len(dq)
                key = -1
                for l in range(p):  // step 2 from the above explanation
                    if dq[p-l-1]>=A[i]:
                        key = p-l
                        break
                if key==-1:
                    dq = []
                else:
                    dq = dq[:key]
                dq.append(A[i])   // add the new element to the queue
                a.append(dq[0]) // store the maximum of the current window
            return a
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.