剑指64-滑动窗口的最大值

Posted on | In |

题目描述

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

暴力求解法。可以扫描每一个滑动窗口的所有数字并找出其中的最大值。如果滑动窗口的大小为k，需要O(k)时间才能找出滑动窗口里的最大值。对于长度为n的输入数组，这个算法总的时间复杂度是O(nk)

1
2
3
4
5
6
7
8
9
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if len(num) == 0 or size <= 0:
            return [] # 注意是返回空的列表，而非None或者0
        res = [] # 注意当len(num) < size时，返回的是空列表，而不装载有是num的最小值的列表
        for i in range(0, len(num) - size + 1):
            res.append(max(num[i:i+size]))
        return res

存在如下低效之处：

  • 窗口里的元素不是都必要，比如[6,2,1,4,5]里的2,1,4在之后的滑动过程中不可能是窗口的最大值，就可以在加入元素5时删掉变成[6,5]。经过这么已处理，滑动窗口的最大值必然在窗口的最左端。
  • 可以用一个队列作为存储窗口。
  • 用一个队列存储窗口。由于需要窗口元素和数组的位置对应，所以队列里存储窗口元素的下标，而不是元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maxInWindows(self, nums, size):
        # 注意当len(num) < size时，返回的是空列表，而不装载有是num的最小值的列表
        if len(nums) < size or size <= 0:
            return []
        stackWin = []
        for i in range(size):
            if i == 0:
                stackWin.append(i)
            else:
                for j in stackWin[::-1]:
                    if nums[j] < nums[i]:
                        stackWin.pop(-1)
                    else:
                        break
                stackWin.append(i)
        maxValues = []
        for i in range(size, len(nums)):
            maxValues.append(nums[stackWin[0]]) # 窗口的第一个必然是最大
            if i - stackWin[0] == size: # 滑出窗口的条件
                stackWin.pop(0)
            for j in stackWin[::-1]:
                if nums[j] <= nums[i]:
                    stackWin.pop(-1)
                else:
                    break
            stackWin.append(i)
        maxValues.append(nums[stackWin[0]])
        return maxValues