LeetCode #239: Sliding Window Maximum

Description:

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. Return the max sliding window.

Follow up:
Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation:

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Solution:

• Method 1: Traverse the array, and simply compare the next element with the maximum element in the window.

  • Time complexity: O((N-k)*k) in worst case, O(N-k) in best case
  • Space complexity: O(k)

• Method 2: Use a monotonic deque to restore the new element if it is larger than the tail of the deque.

  • Time complexity: O(N-k)
  • Space complexity: O(k)

class Solution:
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        method = 'deque'  # ['deque', 'simple']

        if len(nums)>0:
            if k==1:
                return nums
            else:
                if method == 'deque':
                    tmp = []
                    maxlist = []
                    for i in range(len(nums)):
                        # only push larger element
                        while tmp and nums[tmp[-1]] < nums[i]:
                            tmp.pop()
                        tmp.append(i)
                        if tmp[0] <= i-k:  tmp.pop(0)
                        if i >= k-1:  maxlist.append(nums[tmp[0]])
                    return maxlist

                if method == 'simple':
                    tmp = nums[0:k]
                    maxlist = [max(tmp)]
                    for i in range(k,len(nums)):
                        if nums[i] > maxlist[-1]:
                            nextmax = nums[i]
                        else:
                            if maxlist[-1] == tmp[0]:
                                nextmax = max(nums[i], max(tmp[1:]))
                            else:
                                nextmax = maxlist[-1]
                        maxlist.append(nextmax)
                        tmp.pop(0)
                        tmp.append(nums[i])
                    return maxlist
        else:
            return []