滑动窗口的最大值python (leetcode)

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值.

解法一
思路双指针，python 的写法

class Solution:
    def maxSlidingWindow(self, nums, k: int):
        if not nums or k == 0:
            return nums
        res = []
        for i in range(k, len(arr) + 1):
            res.append(max(arr[i - k:i]))
        return res
        

解法二
使用双端队列

• 思路

双端队列的对头始终保存窗口范围内的最大值的下标

class Solution2:
    def maxSlidingWindow(self, nums, k: int):
        if not nums or k == 0:
            return nums
        from collections import deque
        tmp = deque() #双端队列
        res = []
        for i in range(len(nums)):
            while tmp and nums[tmp[-1]] <= nums[i]:
                tmp.pop()
            tmp.append(i)
            # 此时的下标是否过期，过期了就释放掉，保存下一个最大值的下标
            if tmp[0] == i - k:
                tmp.popleft()
            if i >= k - 1:
                res.append(nums[tmp[0]])
        return res