滑动窗口最大值算法实现

“滑动窗口的最大值问题的算法解析与C++实现” 滑动窗口最大值问题是一个常见的计算机算法问题，通常出现在数据结构和算法的面试或编程竞赛中。该问题的目标是从一个给定的整数数组（或序列）中找到所有指定大小的连续子数组（也称为窗口）的最大值，并将这些最大值存储在一个结果数组中。在这个问题中，滑动窗口的大小是固定的，由变量`k`表示。 例如，给定数组`[2, 3, 4, 2, 6, 2, 5, 1]`和滑动窗口大小`k = 3`，我们需要找到六个大小为3的子数组的最大值，它们分别是`[2, 3, 4]`、`[3, 4, 2]`、`[4, 2, 6]`、`[2, 6, 2]`、`[6, 2, 5]`和`[2, 5, 1]`，对应的最大值依次为`4`、`4`、`6`、`6`、`6`和`5`。最终输出的结果数组是`[4, 4, 6, 6, 6, 5]`。 解决滑动窗口最大值问题的关键在于使用一个单调队列（Monotonic Queue）。单调队列是一种特殊的队列，始终保持队列中的元素按照某种单调性（在这里是递增）排列。在本问题中，我们使用一个双端队列（deque）来实现这个单调队列，队列的头部始终保存当前窗口内的最大值。 参考答案提供的C++代码如下： ```c++ class Solution { public: vector<int> maxInWindows(vector<int>& nums, int k) { vector<int> res; deque<int> q; // 遍历数组 for (int i = 0; i < nums.size(); i++) { // 如果队头元素不在当前窗口内，移除它 if (!q.empty() && i - q.front() >= k) q.pop_front(); // 维护队列的单调性，移除所有小于当前元素的队尾元素 while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back(); // 将当前元素的索引入队 q.push_back(i); // 当前窗口已经完整，取出队头元素作为最大值 if (i >= k - 1) { res.push_back(nums[q.front()]); } } return res; } }; ``` 这段代码的工作原理如下： 1. 初始化结果数组`res`和单调队列`q`。 2. 遍历数组`nums`，对于每个元素`nums[i]`： a. 如果队头元素`q.front()`对应的索引不在当前窗口内（即`i - q.front() >= k`），则将其从队列中移除。 b. 清除队列中所有小于`nums[i]`的元素，保持队列单调递增。 c. 将`nums[i]`的索引入队。 d. 如果当前窗口已经完整（即`i >= k - 1`），将队头元素（即当前窗口的最大值）添加到结果数组`res`。 3. 返回结果数组`res`。 通过使用单调队列，我们可以在线性时间复杂度O(n)内解决滑动窗口最大值问题，其中n是输入数组的长度。这种方法避免了在每个窗口中重新扫描整个数组以查找最大值，从而提高了效率。