题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路
思路一： 利用python的max方法计算每个窗口的最大值，时间复杂度O（n*size）。
思路二：使用双向队列，时间复杂度O(n).构建一个辅助的队列，队列记录元素的索引。遍历原数组，对于每一个元素，如果比队列中队尾的数据大，就把队尾的元素删除，直到队内元素都比当前元素大。这样保证，队首的元素是最大的。剩下的操作就是保证队首的元素不过期就行，及时将超过窗口size的队首元素删除。
代码
思路一代码
class Solution:
def maxInWindows(self, num, size):
# write code here
if size > len(num) or size == 0:
return []
result = []
for i in range(len(num)):
if (i+size)> len(num):
break
current_win = num[i:i+size]
value = max(current_win)
result.append(value)
return result
思路二代码
class Solution:
def maxInWindows(self,num, size):
if size == 0 or len(num) == 0:
return []
q = [] # 用来存放最大值的队列(存放的不是值，是该值对应的num索引)
result = []
for i in range(len(num)):
print('current q',q)
if len(q)>0:
#先剔除超出窗口的元素
if (i-q[0])> (size-1):
q.pop(0)
#如果当前元素比队尾元素要大，剔除队尾元素
while len(q) > 0 and num[i] >= num[q[-1]]:
q.pop(-1)
#每个元素只执行了一次的入队操作，所以复杂度是O(n)
q.append(i)
#应对刚开始遍历元素不足size数量的情况。
if i >= size-1:
result.append(num[q[0]])
return result
