POJ 2823 Sliding Window​ 题解《挑战程序设计竞赛》

POJ 2823 Sliding Window 

滑动最大小最值：给定长度为n的数组，求长度为k的滑动窗口内的最大最小值。

4.4常用技巧精选（二） 

双端队列 

没什么好说的，把书上的模板简单拓展一下就行了：

#include <iostream>

#define MAX_N 1000000 + 16
// 输入
int n, k;
int a[MAX_N];

int b[2][MAX_N];// 最小值与最大值
int deq[2][MAX_N];  // 单增单减两个双端队列

void solve()
{
    int s[2], t[2];  // 双端队列的头部和末尾
    memset(s, 0, sizeof(s)), memset(t, 0, sizeof(t));

    for (int i = 0; i < n; i++)
    {
        // 在双端队列的末尾加入i
        while (s[0] < t[0] && a[deq[0][t[0] - 1]] >= a[i])
            t[0]--;
        deq[0][t[0]++] = i;
        while (s[1] < t[1] && a[deq[1][t[1] - 1]] <= a[i])
            t[1]--;
        deq[1][t[1]++] = i;

        if (i - k + 1 >= 0)
        {
            b[0][i - k + 1] = a[deq[0][s[0]]];
            b[1][i - k + 1] = a[deq[1][s[1]]];

            if (deq[0][s[0]] == i - k + 1)
            {
                // 从双端队列的头部删除元素
                s[0]++;
            }
            if (deq[1][s[1]] == i - k + 1)
            {
                // 从双端队列的头部删除元素
                s[1]++;
            }
        }
    }

    for (int i = 0; i <= n - k; i++)
    {
        printf("%d%c", b[0][i], i == n - k ? '\n' : ' ');
    }
    for (int i = 0; i <= n - k; i++)
    {
        printf("%d%c", b[1][i], i == n - k ? '\n' : ' ');
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", a + i);
    }
    solve();
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2823 Sliding Window​ 题解《挑战程序设计竞赛》