LeetCode: Sliding Window Maximum

Sliding Window Maximum

Similar Problems:

• LeetCode: Constrained Subset Sum
• Min Stack
• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #monotone, #slidingwindow

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,

Given nums = [1,3,-1,-3,5,3,6,7], and k = 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?

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Useful link: monotonic queue problem

## https://code.dennyzhang.com/sliding-window-maximum
## Basic Ideas: sliding window with decreasing sequence
##
## Complexity: Time O(n), Space O(k)
class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        import collections
        res = []
        queue = collections.deque()
        for i in range(len(nums)):
            # remove the number
            if len(queue)!=0 and queue[0] == i-k:
                queue.popleft()

            # keep the window decreasing
            while len(queue) != 0 and nums[i] >= nums[queue[-1]]:
                queue.pop()

            # we need to add the new number in all cases
            queue.append(i)

            # already have k numbers
            if i >= k-1: res.append(nums[queue[0]])
        return res