239 Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example, Givennums=[1,3,-1,-3,5,3,6,7], andk= 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as[3,3,5,5,6,7].

Note: You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up: Could you solve it in linear time?

The Idea: Use a sliding window that maintains a window size of length k and use the left and right elements of that window whether to determine whether to pop or add elements to that window. The algorithm goes as follows:

In the first stage, we take a look at the first k elements in the array. Because the window size here will be limited to k, we only need to consider maximum elements that come in and not whether we will exceeds out of bounds of k. Generally speaking, the left of the deque will maintain the current maximum of the window, so when a new element comes in, it first measures against the right of the deque. If this new element exceeds this value, then the right element can be removed because in the current window of size k there is a value that exceeds it, and we are only interested in maximum values. The same goes with the remainder of the deque. Since the deque will only retain a window size of length k, if a new value that comes in exceeds all the values in the deque, then it is true that for the next k position, ALL of the elements in the deque will be exceeded by the new value. Therefore, they can become removed.

In the second stage, we have to make sure that our window maintains the bounds of k. Since we append at most one value at a time, then we will at most need to move one value from the left of the deque if it's index is more than k distance with the current index.

Complexity: O(n) time since we delete and insert a maximum of n elements in the deque. O(k) space for maintaining the size of the deque.

from collections import deque


class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        if k > len(nums) or k <= 0 or not nums:
            return []
        elif k == len(nums):
            return [max(nums)]

        d = deque()
        for i, n in enumerate(nums[0:k]):
            # don't have to worry about exceeding bounds of window
            # just maintain the maximum element in front of deque
            # more recent maximums will make previous maximums irrelevant
            # in the current k window
            while len(d) != 0 and n > nums[d[-1]]:
                d.pop()
            d.append(i)

        # iterate through the remaining elements
        sol = []
        for i, n in enumerate(nums[k:], k):
            # maintain a window size of length k (resize deque)
            # the current front must be the maximum element
            sol.append(nums[d[0]])
            if len(d) != 0 and i - d[0] >= k:
                d.popleft()
            while len(d) != 0 and n > nums[d[-1]]:
                d.pop()
            d.append(i)
        if len(d) != 0:
            sol.append(nums[d[0]])
        return sol


t1, k1 = [], 0
t2, k2 = [1], 1
t3, k3 = [1, 2, 3, 4], 2
t4, k4 = [4, 3, 2, 1], 2
t5, k5 = [1, 3, -1, -3, 5, 3, 6, 7], 3

obj = Solution()
print(obj.maxSlidingWindow(t3, k3))  # [2,3,4]
print(obj.maxSlidingWindow(t1, k1))  # []
print(obj.maxSlidingWindow(t2, k2))  # [1]
print(obj.maxSlidingWindow(t4, k4))  # [4,3,2]
print(obj.maxSlidingWindow(t5, k5))  # [3,3,5,5,6,7]