362. 滑动窗口的最大值
中文
English
给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。
样例
样例 1:
输入:
[1,2,7,7,8]
3
输出:
[7,7,8]
解释：
最开始，窗口的状态如下：`[|1, 2 ,7| ,7 , 8]`, 最大值为 `7`;
然后窗口向右移动一位：`[1, |2, 7, 7|, 8]`, 最大值为 `7`;
最后窗口再向右移动一位：`[1, 2, |7, 7, 8|]`, 最大值为 `8`.
样例 2:
输入:
[1,2,3,1,2,3]
5
输出:
[3,3]
解释:
最开始，窗口的状态如下： `[|1,2,3,1,2 | ,3]` , 最大值为`3`;
然后窗口向右移动一位.`[1, |2,3,1,2,3]`, 最大值为 `3`;
挑战
O(n)时间，O(k)的额外空间
算法 单调队列（看代码吧，还是需要逻辑非常清晰才可以搞定的）
- 单调队列中的元素是严格单调的。我们在求解这个问题的时候需要维护他的单调性。
- 队首元素即为当前位置的最大值。假设要求滑动窗口中的最大值。我们就需要确保滑动窗口中的元素从队首到队尾是递减的。
- 每滑动一次就判断当前元素和队尾元素的关系，如果放入队尾满足单调递减，那么放入即可；如果放入不满足，就需要删除队尾元素直到放入当前元素之后满足队列单调递减。同时要确保已经出窗口的最大值（队首元素）被删除掉。
注意事项：
我们在本题中 往单调队列里压入的是元素对应的下标，因为我们要通过下标来判断该元素有没有离开了滑动窗口，如果离开了滑动窗口就得从队列里给删除了
class Solution:
"""
@param nums: A list of integers.
@param k: An integer
@return: The maximum number inside the window at each moving.
"""
def maxSlidingWindow(self, nums, k):
# write your code here
q = collections.deque()
ans = []
for i,n in enumerate(nums):
while q and q[-1] < n:
q.pop()
q.append(n)
if i >= k and nums[i-k] == q[0]:
q.popleft()
if i >= k-1:
ans.append(q[0])
return ans