首页 > 代码库 > poj-2823 单调队列
poj-2823 单调队列
单调队列理解：参考博客地址：http://blog.csdn.net/justmeh/article/details/5844650
本题参考代码：http://blog.csdn.net/alongela/article/details/8229659
以下为自己整理思路而写，若想获得深刻的理解，可参考以上地址
单调队列：
百度百科：
单调队列，即单调递减或单调递增的队列。使用频率不高，但在有些程序中会有非同寻常的作用。
循环计算最值由于数据量太大会超时，所以要用到单调队列
求最大值，前i-1个数已经排好了一个递减数列，现在要插入第i个数，从末尾往前比较，如果数列中的末尾数小于a[i],由于以后都不可能取到这个数，于是将它删除，直到有一个比a[i]大或者等于的数，就把a[i]放到这个数后面这样比a[i]小的数就不存在了，排在第一个数就是现存数据中最大值，但是其中可能存在不在窗口的数据，所以从第一个数据往后排查，如果该数据在原来数组的下标不满足现在窗口的下标范围，就删除，直到遇到一个在现窗口的数据（如果不是最大值就不用排查了，反正也影响不了），等到要取数据的时候去排在最前面的就行了
代码如下：
#include <iostream> #include <cstdio> #define maxn 1000005 struct Node { int num, id; Node(int a = 0, int b = 0):num(a), id(b){} }; Node maxque[maxn], minque[maxn]; int minans[maxn], maxans[maxn], cur, maxhead, maxend, minhead, minend; int n, k; int main() { scanf("%d%d", &n, &k); minhead = minend = maxhead = maxend = 0; cur = 0; for(int i = 0; i < k; i++) { int x; scanf("%d", &x); while(maxhead < maxend && maxque[maxend - 1].num <= x)maxend--; while(minhead < minend && minque[minend - 1].num >= x)minend--; maxque[maxend] = Node(x, i); minque[minend] = Node(x, i); maxend++; minend++; } for(int i = k; i <= n; i++) { maxans[cur] = maxque[maxhead].num; minans[cur] = minque[minhead].num; cur++; if(i == n)break; int x; scanf("%d", &x); Node p(x, i); while(maxhead < maxend && maxque[maxend - 1].num <= x)maxend--; while(minhead < minend && minque[minend - 1].num >= x)minend--; maxque[maxend] = Node(x, i); minque[minend] = Node(x, i); maxend++; minend++; while(maxhead < maxend && maxque[maxhead].id <= i - k)maxhead++; while(minhead < minend && minque[minhead].id <= i - k)minhead++; } for(int i = 0; i < cur; i++) { printf("%d%c", minans[i], i == cur - 1 ? ‘\n‘ : ‘ ‘); } for(int i = 0; i < cur; i++) { printf("%d%c", maxans[i], i == cur - 1 ? ‘\n‘ : ‘ ‘); } return 0; }
注意，不要用cin输入数据，否则会超时。。。
poj-2823 单调队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。