Sliding Window Maximum - Leetcode Solution

The problem "Sliding Window Maximum" on LeetCode asks us to find the maximum element in each sliding window of size k in an array of integers. To solve this problem, we can use a data structure called a deque.

A deque (short for double-ended queue) is a data structure that supports inserting and deleting elements from both ends in constant time. We can use a deque to keep track of the maximum element in the current sliding window. We will store the indices of the elements in the deque instead of the actual values, so we can efficiently remove elements that are outside of the current window.

Algorithm:

1. Initialize an empty deque.
2. Iterate through the first k elements of the array and add their indices to the deque in decreasing order of their values. We store indices instead of values to be able to remove elements that are outside the current window.
3. For each remaining element in the array, we remove elements from the deque that are outside the current window (i.e., their indices are less than i-k+1).
4. We then remove all elements from the deque that are smaller than the current element, as they cannot be the maximum element in the current window.
5. Add the index of the current element to the deque.
6. The maximum element in the current window is the first element in the deque.
7. Add the maximum element to the output array.
8. Return the output array.

Here is the Python code that implements this algorithm:

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []
        deque = deque()
        
        for i in range(k):
            while deque and nums[i] >= nums[deque[-1]]:
                deque.pop()
            deque.append(i)
        
        for i in range(k, len(nums)):
            output.append(nums[deque[0]])
            
            while deque and deque[0] <= i-k:
                deque.popleft()
            while deque and nums[i] >= nums[deque[-1]]:
                deque.pop()
            deque.append(i)
            
        output.append(nums[deque[0]])
        
        return output

The time complexity of this algorithm is O(n), as each element is added and removed from the deque only once. The space complexity is O(k), as the deque stores at most k indices.

1