LeetCode 239 滑动窗口最大值

LeetCode 239 滑动窗口最大值

问题描述

给定一个整数数组 nums 和一个整数 k，定义一个大小为 k 的滑动窗口，该窗口从数组的最左侧移动到最右侧。你可以看到在滑动窗口内的 k 个数字，并返回滑动窗口中的最大值。

解题思路

我们可以利用一个双端队列 deque 来解决这个问题。在滑动窗口的过程中，我们需要做以下几件事情：

1. 维护一个双端队列 deque，用来存储数组元素的索引。
2. 当新的元素进入滑动窗口时，我们需要从队列的尾部开始比较，将小于等于当前元素值的索引全部弹出，确保队列中的元素是按照递减顺序排列的。
3. 将当前元素的索引入队。
4. 判断队列中的头部元素（即最大值的索引）是否已经超出滑动窗口的范围，若超出范围则将其弹出。
5. 滑动窗口移动到达有效位置后，将队列头部元素对应的数组值添加到结果中。

代码实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq = {};
        vector<int> result = {};
        for (int i = 0; i < nums.size(); i++) {
            // 插入数值
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            dq.push_back(i);    // 入队
            // 滑动窗口右移
            if (i - dq.front() >= k) {    // 队首已经离开窗口了
                dq.pop_front();
            }
            // 记录答案
            if (i >= k - 1) {
                // 由于队首到队尾单调递减，所以窗口最大值就是队首
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

算法复杂度分析

• 时间复杂度：该算法只需一次遍历数组，时间复杂度为 $O(n)$，其中 $n$ 是数组的长度。
• 空间复杂度：双端队列的最大空间为 $O(k)$，用于存储滑动窗口的索引值。

总结

本文介绍了一种使用双端队列来解决滑动窗口最大值的问题的方法。通过维护一个单调递减的双端队列，可以在 $O(n)$ 的时间复杂度内解决该问题，其中 $n$ 是数组的长度。这种方法在面对滑动窗口问题时具有较高的效率和可读性，是一种常见的解题思路。