首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

什么是单调队列算法?详述单调队列算法的原理?用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元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券