PYTHON O(n) deque solutuion


  • 2
    4
    class Solution:
        # @param {integer[]} nums
        # @param {integer} k
        # @return {integer[]}
        def maxSlidingWindow(self, nums, k):
            if nums == []:
                return []
            ans,tmp = [], []
            for i in range(0, k):
                while tmp != [] and nums[i] > nums[tmp[-1]]:
                    tmp.pop()
                tmp.append(i)
            for i in range(k, len(nums)):
                ans.append(nums[tmp[0]])
                while tmp != [] and nums[i] > nums[tmp[-1]]:
                    tmp.pop()
                tmp.append(i)
                while tmp != [] and tmp[0] <= i-k:
                    tmp.pop(0)
            ans.append(nums[tmp[0]])
            return ans

  • 0
    M
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.