“滑动窗口的最大值问题的算法解析与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是输入数组的长度。这种方法避免了在每个窗口中重新扫描整个数组以查找最大值，从而提高了效率。
我的内容管理
展开
