滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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