Leetcode 239. Sliding Window Maximum

https://leetcode.com/problems/sliding-window-maximum/

The hard point is to achieve O(n) time. Actually we can smell a sense of queue here. Python has a quite powerful deque data structure, and we can use that. Still using max() is too slow, we should link the whole process.

Solution:

# T:O(n) S:O(k)
from collections import deque

class Solution:
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer[]}
    def maxSlidingWindow(self, nums, k):
        q = deque()
        max_numbers = []

        for i in xrange(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

        for i in xrange(k, len(nums)):
            max_numbers.append(nums[q[0]])

            while q and nums[i] >= nums[q[-1]]:
                q.pop()

            while q and q[0] <= i - k:
                q.popleft()

            q.append(i)

        if q:
            max_numbers.append(nums[q[0]])

        return max_numbers

Run Time: 208 ms