一、题目内容
题目要求在一个整数数组 nums 中，使用一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧，每次只向右移动一位，返回滑动窗口中的最大值。
二、题目分析
输入和输出
输入：
一个整数数组
nums，表示给定的数组。一个正整数
k，表示滑动窗口的大小。
输出：
一个整数数组，表示每个滑动窗口中的最大值。
算法逻辑 使用双端队列（deque）来解决这个问题。双端队列可以高效地维护窗口内的最大值。
初始化一个双端队列
dq，用于存储窗口内的元素索引。初始化一个结果数组
result，用于存储每个窗口的最大值。遍历数组：
如果队列不为空且队列头部的索引已经超出当前窗口范围，则移除队列头部。
如果队列不为空且当前元素大于队列尾部的元素，则移除队列尾部的元素（因为这些元素在后续窗口中不可能成为最大值）。
将当前元素的索引加入队列。
如果当前索引大于等于
k - 1，则将队列头部的元素值加入结果数组（队列头部始终是当前窗口的最大值）。
返回结果数组。
三、解题要点
双端队列的定义 双端队列是一种可以在两端进行插入和删除操作的队列。在本题中，双端队列用于维护窗口内的最大值。
队列的维护
移除超出窗口范围的元素：如果队列头部的索引已经超出当前窗口范围，则移除队列头部。
移除不可能成为最大值的元素：如果队列不为空且当前元素大于队列尾部的元素，则移除队列尾部的元素。
算法复杂度
时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被插入和移除一次。
空间复杂度：O(k)，双端队列最多存储 k 个元素。
四、代码解答
以下是使用双端队列算法的 C++ 实现代码：
class Solution {
public:
std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
std::vector<int> result;
std::deque<int> dq; // 双端队列，存储元素索引
for (int i = 0; i < nums.size(); ++i) {
// 移除超出窗口范围的元素
if (!dq.empty() && dq.front() < i - k + 1) {
dq.pop_front();
}
// 移除不可能成为最大值的元素
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
// 将当前元素的索引加入队列
dq.push_back(i);
// 当窗口大小达到 k 时，记录最大值
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
};以下是 C 语言实现代码：
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
*returnSize=numsSize-k+1;
int *ret=malloc(sizeof(int)*(*returnSize));
int *queue=malloc(sizeof(int)*numsSize);
int front=0,rear=0,idx=0;
for (int i = 0; i < numsSize; i++)
{
while (front<rear&&queue[front]<=i-k)
{
front++;
}
while (front<rear&&nums[i]>=nums[queue[rear-1]])
{
rear--;
}
queue[rear++]=i;
if (i>=k-1)
{
ret[idx++]=nums[queue[front]];
}
}
return ret;
}
五、详细注释
双端队列的作用
队列头部始终存储当前窗口的最大值的索引。
队列尾部存储当前窗口中可能成为最大值的元素的索引。
队列的维护
移除超出窗口范围的元素：确保队列中的索引始终在当前窗口范围内。
移除不可能成为最大值的元素：确保队列中的元素始终是当前窗口中最大的。
终止条件
当遍历完整个数组时，结束循环。
返回值
返回一个数组，包含每个滑动窗口的最大值。
六、代码执行过程示例
假设我们有一个数组 nums = [1, 3, -1, -3, 5, 3, 6, 7] 和窗口大小 k = 3。
代码执行过程：
初始状态：
dq为空，result为空。
遍历数组：
i = 0，nums[0] = 1：dq= [0]，result= []
i = 1，nums[1] = 3：移除
dq中小于 3 的元素，dq= [1]，result= []
i = 2，nums[2] = -1：移除
dq中小于 -1 的元素，dq= [1, 2]，result= [3]
i = 3，nums[3] = -3：移除
dq中小于 -3 的元素，dq= [1, 2, 3]，result= [3, 3]
i = 4，nums[4] = 5：移除
dq中小于 5 的元素，dq= [4]，result= [3, 3, 5]
i = 5，nums[5] = 3：移除
dq中小于 3 的元素，dq= [4, 5]，result= [3, 3, 5, 5]
i = 6，nums[6] = 6：移除
dq中小于 6 的元素，dq= [6]，result= [3, 3, 5, 5, 6]
i = 7，nums[7] = 7：移除
dq中小于 7 的元素，dq= [7]，result= [3, 3, 5, 5, 6, 7]
最终结果：
返回的数组为
[3, 3, 5, 5, 6, 7]，表示每个滑动窗口的最大值。