双端队列的运用——《挑战程序设计竞赛》

滑动最小值
给定一个长度为n的数列$a_0, a_1, \cdots, a_{n-1}$和一个整数k。求数列$bi = \min{a_i,a{i+1},\cdots,a_{i+k-1} }(i=0,1,\cdots,n-k)。
限制条件：
$1\le k \le n \le 10^6$, $0 \le a_i \le 10^9$

使用双端队列可以在O(n)时间内解决这个问题。最开始时双端队列为空，然后不断维护双端队列使它按照下面的顺序，存储用于计算后面的最小值a的元素的下标。

$$设双端队列从头部开始的元素的值为x_i，则x_i < x_{i+1}且a_i < a_{i+1}$$

// 输入
int n, k;
int a[MAX_N];

int b[MAX_N]; //保存答案的数组
int deq[MAX_N];

void solve()
{
	int s = 0, t = 0; //双端队列的头部和尾部
	for(int i=0;i<n;i++)
	{
		while(s<t && a[deq[t-1]] >= a[i]) t--;
		deq[t++] = i;
		if(i-k+1 >= 0)
		{
			b[i-k+1] = a[deq[s]];
			if(deq[s] == i-k+1)
			{//从双端队列的头部删除元素
				s++;
			}
		}
	}
	for(int i=0;i<=n-k;i++)
	{
		printf("%d%c",b[i],i==n-k?'\n':' ');
	}
}