洛谷：P1886：滑动窗口 /【模板】单调队列

题目

P1886：滑动窗口 /【模板】单调队列

分析

本题是一个练习单调队列的样板，而使用STL中的deque将大大降低代码量，并提升程序的稳健性。

以下仅分析滑动窗口中最大值的核心思路，最小值的算法与此类似。

for (int i = 0; i < n; ++i)
{
    // 处理最小值队列，移除队列中所有大于当前元素的值，保持单调性
    // ...
    // 处理最大值队列，移除队列中所有小于当前元素的值，保持单调性
    while (!max_q.empty() && a[max_q.back()] < a[i])
    {
        max_q.pop_back();
    }
    max_q.push_back(i);
    // 移除两个队列中超出窗口范围的元素
    // ...
    // 以下仅为最大值队列的处理
    if (max_q.front() <= i - k)
    {
        max_q.pop_front();
    }
    // 当窗口形成后，记录最小值和最大值
    if (i >= k - 1)
    {
        // ...
        max_values.push_back(a[max_q.front()]);
    }
}

答案

思考

（略）