滑动窗口最大值

滑动窗口最大值

问题背景

LeetCode 239. 滑动窗口最大值
给定一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。在每个位置，你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

需要返回滑动窗口中的最大值。

相关知识

在解决这个问题之前，我们需要了解滑动窗口的概念。

滑动窗口

滑动窗口是一种常用的数据处理技巧，通常用于处理连续数据序列。它包括一个固定大小的窗口，通过窗口在数据序列上的滑动，对窗口内的数据进行操作。在本问题中，滑动窗口的大小为 k。

问题介绍

给定一个整数数组 nums 和一个整数 k，需要找到滑动窗口中的最大值。

解题思路

解决这个问题的一种常用方法是使用双端队列（deque）。

具体步骤如下：

1. 初始化一个双端队列 deque 用于存储滑动窗口内的元素。还需要初始化一个空列表 ans 用于存储最大值。
2. 首先，遍历数组 nums 的前 k-1 个元素，并根据需要将队列中的较小元素移除。
3. 接下来，从第 k 个元素开始遍历数组 nums：
   • 如果队列的首个元素等于滑动窗口的左侧元素（即超出窗口范围的元素），则将该首个元素从队列中移除。
   • 继续将队列尾部小于当前元素的元素移除。
   • 将当前元素加入队列。
   • 每次遍历都将队列首个元素添加到结果列表 ans 中，因为它是当前滑动窗口的最大值。
4. 返回列表 ans，其中包含滑动窗口中的最大值。

代码实现

下面是 Python 代码的实现，包括注释说明：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if nums is None or len(nums) == 0:
            return []
        
        n = len(nums)
        if k == 1:
            return nums
        elif k == n:
            return [max(nums)]
        
        # 初始化一个双端队列用于存储窗口内的元素
        deque = collections.deque()
        ans = []

        for i in range(k-1):
            while deque and deque[-1] < nums[i]:
                # 如果队尾元素小于当前元素，将其移出队列
                deque.pop()
            
            # 将当前元素加入队列
            deque.append(nums[i])

        for i in range(k-1, n):
            if deque[0] == nums[i-k]:
                # 如果队首元素等于窗口左侧的元素，将其移出队列
                deque.popleft()

            while deque and deque[-1] < nums[i]:
                # 移除队列尾部小于当前元素的元素
                deque.pop()

            # 将当前元素加入队列
            deque.append(nums[i])

            # 将队首元素（最大值）添加到结果列表
            ans.append(deque[0])
        
        return ans

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
35
36
37
38
39
40

时间和空间复杂度

• 时间复杂度：遍历一次数组，时间复杂度为 O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：使用了一个双端队列 deque，它的大小最多为 k，因此空间复杂度为 O(k)。

结论

滑动窗口最大值是一个常见的数组处理问题。本文介绍了解决该问题的方法，并提供了详细的代码实现和注释说明。希望本文对理解滑动窗口技巧和解决类似问题有所帮助。