滑动窗口算法求数组最大值：C++代码实现及解析

题目描述：

给定一个长度为n的数组nums和一个正整数k，求出nums中所有长度为k的连续子数组的最大值。

输入格式：

第一行包含一个整数n和一个正整数k，表示数组长度和子数组长度。

第二行包含n个整数，表示数组nums。

输出格式：

输出一个长度为n-k+1的数组，其中第i个元素表示nums中以i为起点的长度为k的子数组的最大值。

样例输入：

7 3
1 3 -1 -3 5 3 6

样例输出：

3 3 5 5 6

解题思路：

我们可以使用一个双端队列来维护一个窗口，每次将窗口向右移动一位。新加入的元素可能会成为窗口中的最大值，也可能不会。我们需要判断新加入的元素是否可能成为窗口中的最大值，如果是，则将队列中比它小的元素全部弹出，因为它们已经不可能成为最大值了。然后将新元素加入队列中，此时队列的头部元素就是当前窗口中的最大值。

代码实现：

deque<int> q;
vector<int> ans;
for (int i = 0; i < n; i++) {
    if (!q.empty() && i - k + 1 > q.front()) q.pop_front();
    while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
    q.push_back(i);
    if (i >= k - 1) ans.push_back(nums[q.front()]);
}
return ans;

算法步骤：

初始化一个双端队列q和一个数组ans，用于存储窗口中的元素索引和结果数组。
循环遍历数组nums，对于每个元素i：
- 如果队列不为空且当前窗口的起始位置i-k+1大于队列头部元素，则弹出队列头部元素，因为该元素已经不在当前窗口内。
- 循环遍历队列，如果队列尾部元素的值小于等于当前元素的值，则弹出队列尾部元素，因为该元素不可能成为窗口中的最大值。
- 将当前元素索引i加入队列尾部。
- 如果当前窗口长度已经达到k，则将队列头部元素对应的nums值加入结果数组ans。
返回结果数组ans。

总结：

滑动窗口算法是解决求连续子数组最大值或最小值等问题的常用方法，其核心是利用双端队列维护一个窗口，并根据元素的大小关系进行调整，以保证队列头部元素始终是当前窗口中的最大值或最小值。