洛谷-P1440 求m区间内的最小值 题解

题目链接：https://www.luogu.com.cn/problem/P1440

首先看题目，需要我们求出每个数的前面m个数中的最小值，比较容易想到在遍历每一个数的时候，遍历前m个数。但通过对数据量的观察可以发现，1<m<=n<2*10^6,暴力的遍历是通过不了题目的。此时考虑使用单调队列加速最小值的求取。

如何维持一个区间的单调队列？

由数组[7,8,1,2,3,4]举个例子维持一个单调递增队列求区间长度为3的区间的最小值。

首先，i=0,队列为空。7进队列，由于队列为空，所以可以直接将7压入队列，满足单调性。此时区间最小值为队头元素7。

然后，i=1，队列对应的元素值为[7]。判断arr[1]与队尾元素大小，7<8，由于8大于7，可以直接加入队列，满足单调性。此时区间最小值为队头元素7。

i=2,队列对应的元素值为[7,8]。判断arr[2]与队尾元素大小，1更小，由于我们需要保持单调性，所以我们让队尾元素出列（从队尾），再次比较，发现队尾元素仍然更大，所以依然让队尾元素出列（从队尾），此时队列已无元素，将arr[2]入队。此时区间最小值为队头元素1。

i=3,队列对应的元素值为[1]。比较后继续入队，此时区间最小值为队头元素1。

i=4,队列对应的元素值为[1,2]。比较后继续入队，此时区间最小值为队头元素1。

i=5,队列对应的元素值为[1,2,3]。此时队列的队头元素由于已经不在维持的区间内，所以，队头出队列。同时继续比较当前元素与队尾元素大小后入队。

为了便于队列判断队列元素是否仍在区间内在实际操作时队列中存储的往往是数组对应的下标，而不是其元素值。

代码：

#include<iostream>
#include<vector>
using namespace std;

vector<int>vec(2000001);
vector<int>ans(2000001);
vector<int>Q(2000001);

int main()
{
int m, n,l=0,r=0;
cin >> n >> m;
for (int i = 0;i < n;i++)
{
cin >> vec[i];
}
ans[0] = 0;
for (int i = 1;i < n;i++)
{
while (l<r && vec[Q[r-1]] >= vec[i - 1])
r--;
Q[r++] = i - 1;
ans[i] = vec[Q[l]];
if (Q[l] == i - m)l++;
}

for (int i = 0;i < n;i++)
{
   cout << ans[i] << '\n';
}
return 0;
}