写一道关于数组的滑动窗口题目解答

题目描述：

给定一个长度为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 q; vector 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