[Leaf] [P1886] 单调队列 / 滑动窗口

p1886-【模板】单调队列-/-滑动窗口---洛谷">P1886 【模板】单调队列 / 滑动窗口 - 洛谷

1. 题面梗概

中译中：给一个长度为 $n$ 的数组和一个宽度为 $k$ 的会滑动窗口。窗口每向右动一格，你都要找出当前窗口内的最大值和最小值。

$1 \leq k, n \leq 10^6$

2. 逻辑推导

暴力枚举的方式是进行 $n - k$ 次循环，每次查找长度为 $k$ 区间的最值，这样的复杂度是 $O( n^2 )$。

这题可以采用 单调队列 来解决，首先队列为空，将元素加入到队列中。

2.1 操作

如果接下来的元素比队尾元素更大，那么将队尾元素出队，直到这个元素不大于队尾元素为止。

在每次新加入元素之前，先要检查队首元素是否过期（在窗口之外），若队首元素过期了，则队首元素需要出队。

2.2 结论

这是单调队列的母题。通过 “及时排除过期元素” 和 “保持队列单调性”，我们将一个区间查询问题转化为了队列头部的 $O(1)$ 读取。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 50;

int n, k;
int a[maxn];

int ans1[maxn];
int ans2[maxn];

int main()
{	
    cin >> n >> k;
    for( int i = 1; i <= n; ++ i )
        cin >> a[i]; 
    
    deque<int> q;
    int cnt = 0;
    for( int i = 1; i <= n; ++ i )
    {
        while( !q.empty( ) && a[ q.back( ) ] >= a[i] )
            q.pop_back( );
        q.push_back( i );
        while( !q.empty( ) && q.front( ) <= i - k )
            q.pop_front( );
        if( i >= k ) ans1[++cnt] =a[ q.front( ) ];
    }
    
    q.clear( );
    cnt = 0;
    for( int i = 1; i <= n; ++ i )
    {
        while( !q.empty( ) && a[ q.back( ) ] <= a[i] )
            q.pop_back( );
        q.push_back( i );
        while( !q.empty( ) && q.front( ) <= i - k )
            q.pop_front( );

        if( i >= k ) ans2[++cnt] = a[ q.front( ) ];
    }

    for( int i = 1; i <= cnt; ++ i )
    {
        cout << ans1[i] << " ";
    }
    cout << '\n';

    for( int i = 1; i <= cnt; ++ i )
    {
        cout << ans2[i] << " ";
    }
    cout << '\n';
    return 0;
}

4. 备注

• 复杂度：$O( N )$。

• Trick：注意队列中存储的是下标，而不是具体的数据本身。

• 关联知识点： 单调队列