HardLeetCode #239Sliding Window

Sliding Window Maximum

You are given an array of integers 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.

Constraints

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

Examples

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

Output: [3,3,5,5,6,7]

Solution

Approach

Use a monotonic decreasing deque. Store indices, remove elements outside window, remove smaller elements from back before adding new element.

from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque()
    result = []
    for i in range(len(nums)):
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Complexity

Time:O(n)

Space:O(k)

Hints

1.A naive approach is O(nk), can we do better?
2.Use a deque to maintain potential maximums
3.Keep deque in decreasing order

Asked at

Google