什么是单调队列算法？详述单调队列算法的原理？用C语言实现单调队列算法。内附完整代码。
大家好，我是贤弟！
一、什么是单调队列算法？
单调队列算法是一种数据结构，主要用于解决滑动窗口类问题，即在一个长度为 nn 的序列中，求每个长度为 mm 的区间的区间最值。
单调队列算法的时间复杂度为 O(n)O(n)，相比 O(n \log n)O(nlogn) 的ST表和线段树在此问题上具有更好的优势。单调队列基本思想是维护一个双向队列(deque)，它的性质是队列的头部或尾部是当前队列元素的极值。
二、单调队列算法的原理
单调队列算法的原理：
我们以找到序列 [1,2,3,2,1,4][1,2,3,2,1,4] 中长度为 33 的滑动窗口的最大值为例说明单调队列算法的原理。先建立一个单调不增的队列，遍历整个序列，在边界时更新窗口的最大值并记录即可。
具体步骤如下：
1、开始遍历整个序列，首先将前 kk 个元素(滑动窗口)插入队列中，并更新队列中的最大值。
2、从第 k+1k+1 个元素开始，将它插入队列末端，然后检查队列头部是否已经超出当前窗口范围，如果是则将头部元素弹出，直到头部元素在窗口范围内或者队列为空。弹出头部元素之后，重新计算队列中的最大值。
重复步骤2直到遍历完整个序列，期间记录所有窗口的最大值。
三、用C语言实现单调队列算法的代码如下：
#include
// 定义结构体作为队列元素typedef struct { int val; // 元素值 int idx; // 元素在原序列中的位置} Element;
// 定义双端队列结构体typedef struct { Element *base; // 队列底层的数组 int front; // 头部指针 int rear; // 尾部指针 int size; // 当前队列大小 int capacity; // 队列容量} Deque;
// 初始化双端队列void initDeque(Deque *dq, int capacity) { dq->capacity = capacity; dq->front = dq->rear = 0; dq->size = 0; dq->base = (Element *)malloc(sizeof(Element) * capacity);}
// 判断双端队列是否为空int isEmpty(Deque *dq) { return dq->size == 0 ? 1 : 0;}
// 判断队列是否已满int isFull(Deque *dq) { return dq->size >= dq->capacity ? 1 : 0;}
// 在队列尾部插入元素void pushBack(Deque *dq, Element e) { if (isFull(dq)) { return; // 队列已满，无法插入元素 } dq->base[dq->rear++] = e; dq->size++;}
// 在队列头部插入元素void pushFront(Deque *dq, Element e) { if (isFull(dq)) { return; // 队列已满，无法插入元素 } dq->base[--dq->front] = e; dq->size++;}
// 弹出队列头部元素Element popFront(Deque *dq) { if (isEmpty(dq)) { Element e; e.val = -1; // 队列为空，返回一个非法值 return e; } dq->size--; return dq->base[dq->front++];}
// 弹出队列尾部元素Element popBack(Deque *dq) { if (isEmpty(dq)) { Element e; e.val = -1; // 队列为空，返回一个非法值 return e; } dq->size--; return dq->base[--dq->rear];}
// 获取队列头部元素Element getFront(Deque *dq) { if (isEmpty(dq)) { Element e; e.val = -1; // 队列为空，返回一个非法值 return e; } return dq->base[dq->front];}
// 获取队列尾部元素Element getBack(Deque *dq) { if (isEmpty(dq)) { Element e; e.val = -1; // 队列为空，返回一个非法值 return e; } return dq->base[dq->rear-1];}
// 释放双端队列void destroyDeque(Deque *dq) { free(dq->base);}
// 单调队列算法void maxSlidingWindow(int* nums, int numsSize, int k, int* result, int* resultSize){ Deque q; // 定义双端队列 Element e; initDeque(&q, numsSize); *resultSize = 0; for (int i = 0; i < numsSize; i++) { if (i >= k && getFront(&q).idx <= i - k) { popFront(&q); // 弹出过期元素 } e.val = nums[i]; e.idx = i; while (!isEmpty(&q) && e.val > getBack(&q).val) { popBack(&q); // 弹出队列中的较小元素 } pushBack(&q, e); // 将新元素插入队列尾部 if (i >= k - 1) { result[(*resultSize)++] = getFront(&q).val; // 记录当前窗口最大值 } } destroyDeque(&q); // 释放双端队列}
// 测试用例int main() { int nums[] = {1,2,3,2,1,4}; int k = 3; int size = sizeof(nums) / sizeof(nums[0]); int result[size-k+1]; int resultSize = 0; maxSlidingWindow(nums, size, k, result, &resultSize); printf("滑动窗口最大值为："); for (int i = 0; i < resultSize; i++) { printf("%d ", result[i]); } printf("\n"); return 0;}
注意：
以上代码中，我们先定义了队列元素的结构体 Element 和双端队列的结构体 Deque。
在 maxSlidingWindow 函数中实现了单调队列算法，并在主函数中调用该函数找到输入序列中长度为 kk 的滑动窗口的最大值。
输出结果如下：
//滑动窗口最大值为：3 3 3 2 4
- 发表于:
- 原文链接：https://page.om.qq.com/page/OyeL7hVwcjZ6mmf4ognkSw-g0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
