hdu 3530 单调队列 **

题意:题意:给你一个长度为n的数列,要求一个子区间,使得区间的最大值与最小值的差s满足,
m<=s<=k,求满足条件的最长子区间

链接:点我

假设数列为:8,7,12,5,16,9,17,2,4,6.N=10,k=3.

那么我们构造一个长度为3的单调递减队列:

首先,那8和它的索引0放入队列中,我们用(8,0)表示,每一步插入元素时队列中的元素如下:

0:插入8,队列为:(8,0)

1:插入7,队列为:(8,0),(7,1)

2:插入12,队列为:(12,2)

3:插入5,队列为:(12,2),(5,3)

4:插入16,队列为:(16,4)

5:插入9,队列为:(16,4),(9,5)

。。。。依此类推

那么f(i)就是第i步时队列当中的首元素:8,8,12,12,16,16,。。。

原文地址:https://www.cnblogs.com/cnblogs321114287/p/4533219.html