滑动窗口最大值

发表于 分类于 阅读次数：

滑动窗口最大值（难度：困难）

1579702056767
1579702078067

方法一：暴力法

遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为 O(Nk)，表现较差。

代码
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) == 0:
            return nums
        res = []
        for i in range(0,len(nums)-(k-1)):
            j = i + k-1
            res.append(max(nums[i:j+1]))
        return res
1579666044377
复杂度
  • 时间复杂度：O(Nk)。其中 N 为数组中元素个数。
  • 空间复杂度：O(N−k+1)，用于输出数组。

方法二：递归

详细讲解见https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetcode-3/

代码
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
30
31
32
33
34
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) <= 1:
            return nums
        
        n = len(nums)
        left = [0]*n
        right = [0]*n
        left[0] = nums[0]
        right[n-1] = nums[n-1]
        
        for i in range(1,n):
            # 从左到右
            if i % k == 0: 
                # block start
                left[i] = nums[i]
            else:
                left[i] = max(left[i-1], nums[i])
            
            # 从右到左
            j = n - i - 1
            if (j+1) % k == 0:
                # block end
                right[j] = nums[j]
            else:
                right[j] = max(right[j+1], nums[j])
        
        res = []
        for i in range(n-k+1):
            j = i+k-1
            res.append(max(right[i], left[j]))
        
        return res

1579669254322
复杂度

时间复杂度：O(N)，我们对长度为 N 的数组处理了 3次。

空间复杂度：O(N)，用于存储长度为 N 的 left 和 right 数组，以及长度为 N - k + 1的输出数组。

方法三：双端队列

1579703855488
1579703901936

思路：维护窗口，向右移动时左侧超出窗口的值弹出，因为需要的是窗口内的最大值，所以只要保证窗口内的值是递减的即可，小于新加入的值全部弹出。最左端即为窗口最大值

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        temp = []
        res = []

        for i,v in enumerate(nums): # i是索引，v是值
            # 左侧超出窗口的值弹出
            if i>=k and temp[0]<=i-k:
                temp.pop(0) # pop索引为0的数
            while temp and nums[temp[-1]] <= v:
                temp.pop() # pop最后一个数
            temp.append(i)
            if i>=k-1:
                res.append(nums[temp[0]])
        return res
1579704974700
复杂度

时间复杂度：O(N)，每个元素被处理两次- 其索引被添加到双向队列中和被双向队列删除。

空间复杂度：O(N)，输出数组使用了O(N−k+1) 空间，双向队列使用了 O(k)。