单调队列——求m区间内的最小值

单调队列，顾名思义是指队列内的元素是有序的，队头为当前的最大值（单调递减队列）或最小值（单调递增序列），以单调递减队列为例来看队列的入队和出队操作：

1、入队：

     如果当前元素要进队，把当前元素和队尾元素比较，如果当前元素小于队尾元素，那么当前元素直接进队，如果当前元素大于队尾元素，那么队尾出队，将当前元素和新的队尾再做比较，直到当前元素大于队尾元素或者队列为空。单调队列只能在队尾插入元素，队尾和队头都可以删除元素。

2、出队：

     出队直接取队头即可，因为用单调队列就是为了取最值，而队头就是最值。

例子：将数组a[] = {3, 5, 2, 8, 1, 4, 7}依次入队，并保证队列为一个 单调递减 队列。

• 3入队，队列为空直接入队，队列元素为：3；
• 5入队，5和队尾比较，5大于3，3出队，队为空，5入队，队列元素为：5；
• 2入队，2和队尾比较，2小于5，直接入队，队列元素为：5，2；
• 8入队，8和队尾比较，2出队，8再和队尾比较，5出队，队为空，8入队，队列元素为：8；
• 1入队，...，队列元素为：8，1；
• 4入队，...，队列元素为：8，4；
• 7入队，...，队列元素为：8，7。

• i = 0，初始队列为空，7入队，队列为：{ 0(7) }， （0为下标，括号为下标对应的值） ，窗口区间为[0]，最大值为队头a[0] = 7；
• i = 1，队头下标没有超出k， 3入队，队列为：{ 0(7), 1(3) }，窗口区间为[0,1]，最大值为队头a[0] = 7；
• i = 2，队头下标没有超出k，2入队，队列为：{ 0{7), 1(3), 2(2) }，窗口区间为[0,1,2]，最大值为队头a[0] = 7；
• i = 3，队头下标为0超出k，删除队头，5入队，队列为：{ 3(5) }，窗口区间为[1,2,3]，最大值为队头a[3] = 5；
• i = 4，队头下标没有超出k，6入队，队列为：{ 4(6) }，窗口区间为[2, 3, 4]，最大值为队头a[4] = 6;
• 窗口继续向右滑动，如果当前队头下标超出范围就删除队头，然后去队头，没有超出范围就直接取队头。

#include
#include
using namespace std;
int n,m,a[2000010];
int q[2000010],h=1,t=1;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);printf("0\n");q[1]=1;for(int i=2;i<=n;i++){printf("%d\n",a[q[h]]);if(q[h]<=i-m)h++;while(a[i]<=a[q[t]]&&t>=h)t--;t++;q[t]=i;}return 0;
}

转载于:https://www.cnblogs.com/widerg/p/7045190.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！