滑动窗口最大值

滑动窗口最大值

Leetcode 239. 滑动窗口最大值 - 力扣（LeetCode） (leetcode-cn.com)

暴力解法：

        每次在滑动窗口中去找最大值

        时间复杂度:O((N-K+1)*n)

代码如下：

def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res=[]
        for i in range(len(nums)):
            maxValue=-10001
            for j in range(i,i+k):
                if i+k-1nums[j] else nums[j]
                else:
                    return res
            res.append(maxValue)
        return res

但是这个会超出时间限制

联想数据结构--大顶堆

        每次在滑动窗口内建立大顶堆 O（logk)

        每次取出堆顶 O（1)

时间复杂度为O（n·logk)

heapq是小顶堆，python里没有可以直接用的库

只扫描一次的做法：12 | 面试题：返回滑动窗口中的最大值 (geekbang.org)

使用一个双端队列维护滑动窗口，该滑动窗口的0号元素始终保持为该滑动窗口的最大值

即新看到的值比队尾元素大时，队尾元素应该出队。

具体如图：

 

 时间复杂度：O(n)

代码如下：

def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []
        window,res=[],[]
        for i in range(len(nums)):
            if i>=k and window[0]=0:
                res.append(nums[window[0]])
        return res