题目
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
进阶：
你能在线性时间复杂度内解决此题吗？
解答
方法一：暴力破解。cur表示窗口，记录最大值，依次后移。时间复杂度O(n·k)，太慢了，才超过30%的代码
方法二：用大顶堆存窗口元素，堆顶就是当前窗口最大值，依次后移，删除最左边，加入一个新元素，堆删除操作时间复杂度O(log(n))，插入操作O(1)，这种方法总的时间复杂度O(n·log(k))。
But！Python中没有大顶堆的实现，用“存入堆、从堆中取出的时候，都用相反数”模拟大顶堆可行，以为这就解决了吗？ No! heapq包可以删除堆顶元素，但没提供删除堆中某元素的方法，所有先找到元素在堆中位置再用了del删除，del删除后，存储堆的列表顺序就不是堆了，需要重新排列成堆，时间复杂度O(n)，所以用Python最后做出来时间复杂度O(n·k)，但这个提交速度为毛没有暴力破解快，无语。。。
方法三：双向队列，时间复杂度O(n)
思路：依次遍历列表中的元素，cur存放已经在窗口中的元素的下标，假如当前元素为c, 则用c和cur中元素从后向前比较，删除cur中小于c的元素，并把c的下标加到cur中，这步操作保证了cur[0]表示的元素永远是窗口中最大的
注：c和cur比较时，一定要从后往前，否则部分样例不能通过：[1, 3, 1, 2, 0, 5], k=3 .........................视频里讲的从前往后：）
通过代码如下：
from heapq import *
class Solution:
# 方法一：暴力破解
# def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# if not nums:
# return []
# ans = []
# cur = []
# for x in range(k):
# cur.append(nums[x])
# ans.append(max(cur))
# while x < len(nums)-1:
# del cur[0] # 删除表头
# cur.append(nums[x+1]) # 添加到尾
# ans.append(max(cur)) # max()的平均时间复杂度是O(n)
# x = x+1
# return ans
# 方法二：大顶堆
# def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# if not nums:
# return []
# l = [] # 预存堆
# ans = []
# for index, x in enumerate(nums):
# if index==0 or len(l)<k: # 堆还没满，入堆
# heappush(l, -x)
# else:
# ans.append(-l[0]) # 堆顶，最小的，取负数刚好是最大的
# del l[l.index(-nums[index-k])] # 删除窗口左侧第一个
# heappush(l, -x) # 入堆
# heapify(l) # 堆貌似乱了......， 重新排列成堆，时间复杂度是O(n)。。。
# ans.append(-l[0])
# return ans
# 方法三：双端队列
def maxSlidingWindow(self, nums, k):
if not nums:
return []
cur = [] # 存窗口元素的index，cur[0]位置永远是最大的
ans = []
for index, x in enumerate(nums):
if index >= k and index - k >= cur[0]: # cur[0]和当前元素的index距离为k，说明cur[0]该从窗口删除了
cur.pop(0)
while cur and x >= nums[cur[-1]]: # 这里，cur要从后往前删小于当前元素的值
cur.pop()
cur.append(index)
if index + 1 >= k: # 当前元素位已经走过了窗口距离大小
ans.append(nums[cur[0]])
return ans