admin 管理员组

文章数量: 887006

[数据结构]手写循环队列解决滑动窗口问题

😀手写双端队列解决滑动窗口问题

问题：

滑动窗口（洛谷1886）
问题简述：有长度为n的序列a，及大小为m的窗口。从左边向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值，例如下图。


测试输入：
8 3
1 3 -1 -3 5 3 6 7
输出：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

问题分析

手写双端队列

本来想通过head和rear两个指针实现双端队列，但是写完后发现队头和队尾的插入始终存在很大问题。参考网友代码后发现，队列中使用head和size计数，用(head+size-1)%N表示rear更为简便。

滑动窗口问题

滑动窗口需要比较出队列中指定m个数中最小、最大值。这里采用的思路是用两个循环，分别比较出最大和最小值，每个元素最多入队1次、出队1次，所以时间复杂度为O(n)。以输出最小值为例，简述思路：
1.用数组a存储所有需要判断的n个数据；用双端队列Q作为滑动窗口，存储m个数据在数组a中的位置（可能是1,2,3…n）
2.保证滑动窗口内有m个数时，输出最小值
3.队首删除Q中，比下一个进入窗口的数字大的数在a中对应的序号;将下一个数字对应的序号存入Q的队尾

代码

//手写双端队列--滑动窗口
#include<iostream>
using namespace std;
#define N 1003
int a[N];//创建双端队列及方法
struct myqueue {//动态分配int *data;//通过head和size计算出尾rear的位置int head, size;//初始化bool init() {Q.data = (int*)malloc(N* sizeof(int));if (!Q.data) return false;head = size = 0;return true;}//front 返回队头int front(){//判断是否为空if (size==0){return -1;}return data[head];}//back 返回队尾int back(){//判断是否为空if (size==0){return -1;}int rear = (head + size - 1 + N) % N;return data[rear];}//pop_back 删除队尾bool pop_back(){//判断队列是否为空if (size==0)return false;size--;return true;}//pop_front 删除队头bool pop_front(){if (size==0)return false;head = (head + 1) % N;size--;return true;}//push_back(e) 从队尾添加一个元素ebool push_back(int e){//判断队列是否已满if (size==N){return false;}size++;int rear = (head + size-1)%N;data[rear] = e;return true;}//push_front(e) 在队头添加一个元素ebool push_front(int e){//判断队列是否已满if (size==N){return false;}size++;head = (head - 1+N) % N;data[head] = e;return true;}bool empty()//判断是否为空{if (size==0)return true;return false;}
}Q;int main()
{int n, m;//n个数，m为窗口大小cin >> n >> m;Q.init();//读取n个数for (int i = 1; i <=n; i++){cin >> a[i];}//输出最小值for (int i = 1; i <=n; i++){//Q不为空，队尾元素大于新的元素，在队列中删除该元素while (!Q.empty() && a[Q.back()] > a[i]){//cout << "尾";//cout << Q.back() << endl;Q.pop_back();}//添加新元素Q.push_back(i);//cout << "i:" << i << endl;//如果Q超过滑动窗口大小，删除头if(i>=m){//保证滑动窗口中仅有m个数while(!Q.empty() && Q.front() <= i - m){//cout << "头";//cout << Q.front() << endl;Q.pop_front();//删去头}cout << a[Q.front()] << " ";}}cout << endl;//输出最大值Q.init();//初始化队列，记录窗口对应的数字在数组中的序号for (int i = 1; i <=n; i++){//cout << "i=" << i << endl;//if(i>1)//cout << "新数" << a[i] << "老的:" << a[Q.back()] << endl;//判断队列中是否有数，且是否全部大于要进来的数while (!Q.empty()&&a[Q.back()]<a[i]){//要进来的数大,删除原来的数//cout << "要进来的数为" << a[i] << endl;//cout << "删除" << a[Q.back()] << endl;Q.pop_back();}//引入新的iQ.push_back(i);//判断窗口是否有三个数if(i>=m){//cout << "i是"<<i<<"超过m了" << endl;//滑动窗口是否<=m个数while (!Q.empty()&&Q.front()<=i-m){//不是，删除前面的数//cout << "数字多了,删除" << Q.front() << endl;Q.pop_front();}//输出//cout << a[Q.front()] << " "<<endl;cout << a[Q.front()] << " ";}}return 0;
}

Tips:

There is always an easy solution to every problem——neat,plausible and wrong.

参考链接：

本文标签： 数据结构手写循环队列解决滑动窗口问题

版权声明：本文标题：[数据结构]手写循环队列解决滑动窗口问题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732362170h1535523.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。