题目描述
给定一个数组和一个滑动窗口的大小，请找出所有滑动窗口里的最大值。例如，如果输入数组 {2，3，4，6，2，5，1} 及滑动窗口的大小 3，那么一定存在 6 个滑动窗口，它们的最大值分别为 {4，4，6，6，6，5}。
解题思路
这个问题最简单的办法自然是暴力求解，每次从一个窗口的起点开始向后遍历k个数字，然后求出最大值，很容易知道这个解法的时间复杂度为O(n^2)，但是题目给定的要求是线性的时间复杂度，也就是O(n)。所以这里自然不能用暴力求解。
实际上，我们可以用一个双端队列来存储当前窗口的最大值。我们创建一个双端队列，这里队列中存储的是窗口最大值的下标。如果队列为空，那么就将当前元素的下标添加到队列中。如果队列不为空，那么就有两种情况。如果当前元素比队尾元素所指向的元素还要大，那么当这个元素进入到滑动窗口，队列尾那些比他小的元素所指向的元素，一定不可能是窗口中的最大值，所以就将队尾这些元素删去，直到队尾元素指向的元素比当前的元素大或者相等，然后将当前元素的下标加入队列。如果当前元素比队尾元素所指向的元素要小或者相等，那么就直接将当前元素的下标加入到队列尾。取的时候，只需要取队列头的元素就可以了，因为那就代表着当前窗口的的最大值。取的时候要判断一下，如果队头元素已经是窗口之外了，那么就要将队头出队。否则直接取队头元素就可以了，它就是窗口中最大值对应的下标。文字很多很抽象，用图中的样例来模拟一下好了。
遍历完第一个窗口的时候，队列的元素为1（3）、2（-1），括号中为最大元素，队列元素为元素的下标。所以当前窗口最大值为3
第二个窗口，-3比-1小，所以将3入队，队列元素为1（3）、2（-1）、3（-3），当前窗口最大值为3
第三个窗口，5比队列中所有元素都要大，所以队列中所有元素被清空，队列元素为4（5），当前窗口最大值为5
第四个窗口，队列元素4（5）、5（3）
第五个窗口，队列元素6（6）
.......
所以找出滑动窗口的最大值的过程，实际上就两步工作：
（1）判断当前的最大值是否过期。
（2）将读入的数字与 temp 中的元素从后向前依次比较大小，将 temp 中小于读入数字的元素都弹出；如果删除后 temp 的大小还没有达到 size - 1，那么将这个元素压入（删除后 temp 的大小有可能达到 size - 1 嘛？有可能的！因为可能经过比较发现 temp 中没有元素被弹出）。
代码实现
class Solution:
def maxInWindows(self,num,size):
if not num:
return []
if size > len(num) or size < 1:
return []
if size == 1:
return num
res = []
temp = [0]
for i in range(len(num)):
if i - temp[0] > size - 1:
temp.pop(0)
while len(temp) > 0 and num[i] >= num[temp[-1]]:
temp.pop()
if len(temp) < size - 1:
temp.append(i)
if i >= size -1:
res.append(num[temp[0]])
return res
京公网安备 11010502036488号