每日一题——滑动窗口的最大值

题目描述

给定一个长度为 n 的数组 num 和滑动窗口的大小 size，找出所有滑动窗口里数值的最大值。

例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 {4, 4, 6, 6, 6, 5}。

示例

示例 1
输入：
[2,3,4,2,6,2,5,1], 3
返回值：
[4, 4, 6, 6, 6, 5]

示例 2
输入：
[9,10,9,-7,-3,8,2,-6], 5
返回值：
[10, 10, 9, 8]

示例 3
输入：
[1, 2, 3, 4], 5
返回值：
[]

说明

• 如果滑动窗口的大小大于数组的长度或者大小为 0，则返回空数组。

解题思路

这个问题可以通过滑动窗口的方式解决，同时需要注意效率和空间复杂度。我们可以使用 双端队列（Deque） 来高效地解决这个问题。

双端队列的特点

• 双端队列可以在 O(1) 的时间复杂度内从两端删除和添加元素。
• 通过双端队列，我们可以在滑动窗口内保持一个有序的队列，其中队列的前端始终是窗口中的最大值。

实现步骤

1. 初始化双端队列：用于保存当前滑动窗口内的元素索引，队列保持单调递减的顺序，即队列中的元素从前到后的值是递减的。
2. 遍历数组：每遍历到一个新的元素时：
   • 移除不在窗口内的元素。
   • 维护队列的递减性质，移除队列中比当前元素小的所有元素。
   • 将当前元素的索引添加到队列中。
   • 当窗口大小达到 size 时，队列前端的元素就是当前窗口的最大值。
3. 返回结果：每次更新窗口后，将最大值添加到结果数组中。

代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>typedef struct {int *data;  // 用于存储队列元素的数组int front;  // 队列头int rear;   // 队列尾
} Deque;// 创建一个空的双端队列
Deque* createDeque(int capacity) {Deque *dq = (Deque*)malloc(sizeof(Deque));dq->data = (int*)malloc(capacity * sizeof(int));dq->front = -1;dq->rear = -1;return dq;
}// 判断队列是否为空
int isEmpty(Deque *dq) {return dq->front == -1;
}// 判断队列是否已满
int isFull(Deque *dq) {return dq->rear == dq->front - 1;
}// 从队列前端删除元素
void popFront(Deque *dq) {if (!isEmpty(dq)) {dq->front++;if (dq->front > dq->rear) {dq->front = dq->rear = -1;  // 队列空时重置}}
}// 从队列后端删除元素
void popBack(Deque *dq) {if (!isEmpty(dq)) {dq->rear--;if (dq->rear < dq->front) {dq->front = dq->rear = -1;  // 队列空时重置}}
}// 从队列前端获取元素
int front(Deque *dq) {return dq->data[dq->front];
}// 向队列后端添加元素
void pushBack(Deque *dq, int value) {if (dq->front == -1) {dq->front = dq->rear = 0;} else {dq->rear++;}dq->data[dq->rear] = value;
}// 滑动窗口最大值的函数
int* maxSlidingWindow(int* nums, int numsSize, int size, int* returnSize) {int *result = (int*)malloc((numsSize - size + 1) * sizeof(int));*returnSize = 0;if (size == 0) {return result;  // 如果窗口大小为0，返回空数组}Deque *dq = createDeque(numsSize);  // 创建双端队列for (int i = 0; i < numsSize; ++i) {// 移除队列中超出窗口范围的元素if (!isEmpty(dq) && front(dq) < i - size + 1) {popFront(dq);}// 移除队列中比当前元素小的元素while (!isEmpty(dq) && nums[front(dq)] <= nums[i]) {popBack(dq);}// 添加当前元素到队列pushBack(dq, i);// 当窗口大小达到 size 时，记录当前窗口的最大值if (i >= size - 1) {result[(*returnSize)++] = nums[front(dq)];}}return result;
}// 测试函数
int main() {int nums[] = {2, 3, 4, 2, 6, 2, 5, 1};int size = 3;int returnSize = 0;int *result = maxSlidingWindow(nums, sizeof(nums) / sizeof(nums[0]), size, &returnSize);for (int i = 0; i < returnSize; ++i) {printf("%d ", result[i]);}free(result);  // 释放结果数组return 0;
}

代码解析

1. 初始化双端队列：

   • 我们使用结构体 Deque 来表示双端队列。队列包含一个动态分配的数组 data 来存储元素，以及 front 和 rear 来表示队列的前端和后端。
   • createDeque 函数用于创建一个空的双端队列。
   • popFront 和 popBack 分别是从队列的前端和后端删除元素。
   • pushBack 是向队列后端添加元素。
   • front 函数返回队列前端的元素。

2. 滑动窗口的最大值函数：

   • maxSlidingWindow 函数是核心逻辑，接收一个数组、窗口大小和数组的大小，并返回一个数组，表示每个滑动窗口的最大值。
   • 使用双端队列来维护当前窗口的最大值。每次窗口滑动时，移除不再窗口范围内的元素，并维护队列的单调性，确保队列中的最大元素总是在队列的前端。

3. 时间与空间复杂度：

   • 时间复杂度：每个元素至多被添加和移除一次，所以时间复杂度是 O(n)，其中 n 是数组的长度。
   • 空间复杂度：队列最多存储 n 个元素，因此空间复杂度是 O(n)。

总结

捣鼓了半天的数组和堆栈，结果发现实现不了，pop和push是最难的，所以还是要老老实实根据教程案例来学习，标新立异没必要。