239. Sliding Window Maximum

Loading...LeetCode

传说中需要使用特殊数据结构来解题的sliding window，本质上还是移动指针、维护一个window，只是通过window获取题目要求的答案时，需要使用特殊的数据结构。

这道题需要把window维护成一个单调queue，每次push元素进来时，比该元素小的已有元素都会被pop出去，这样queue的第一个元素就永远是window的最大值。

class Solution:
    def maxSlidingWindow(self, nums, k):
        window = collections.deque()
        ans = []
        
        for i in range(len(nums)):
            # 比右指针元素小的就pop掉
            while window and nums[i] >= nums[window[-1]]:
                window.pop()
            
            window.append(i)
            
            # 当右指针超过k，就开始填写结果
            if i >= k - 1: 
                ans.append(nums[window[0]])
            
            # 当window size 超过k，移动左指针
            if i + 1 - window[0] == k: 
                window.popleft()
                
        return ans