Description

An array of size n ≤ 106 is given to you. There is a sliding window of
size k which is moving from the very left of the array to the very
right. You can only see the k numbers in the window. Each time the
sliding window moves rightwards by one position. Following is an
example: The array is [1 3 -1 -3 5 3 6 7],and k is 3. Window
position Minimum value Maximum value [1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3
-1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 Your task is to determine the maximum and minimum
values in the sliding window at each position.

Input

The input consists of two lines. The first line contains two integers
n and k which are the lengths of the array and the sliding window.
There are n integers in the second line.

Output

There are two lines in the output. The first line gives the minimum
values in the window at each position,from left to right,
respectively. The second line gives the maximum values.

Sample Input

8 3
1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路

这是著名的滑动窗口问题，就是单调队列的基本问题。。这道题主要说一下单调队列解法

单调队列的一般问题是这么描述的：

给定一个长度为N的整数数列a(i),i=0,1,…,N-1和窗长度k.

要求：

f(i) = max{a(i-k+1),a(i-k+2),...,a(i)},i = 0,N-1

问题的另一种描述就是用一个长度为k的窗在整数数列上移动，求窗里面所包含的数的最大值。

解法一：

很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。

这种方法每求一个f(i),都要进行k-1次的比较，复杂度为O(N*k)。

那么有没有更快一点的算法呢？

解法二：

我们知道，上一种算法有一个地方是重复比较了，就是在找当前的f(i)的时候，i的前面k-1个数其它在算f(i-1)的时候我们就比较过了。那么我们能不能保存上一次的结果呢？当然主要是i的前k-1个数中的最大值了。答案是可以，这就要用到单调递减队列。

单调递减队列是这么一个队列，它的头元素一直是队列当中的最大值，而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素，可以从队列的两端删除元素。

1. 首先看插入元素：为了保证队列的递减性，我们在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v,则删除队尾的元素，然后继续将新的队尾的元素与v比较，直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2. 队尾的删除刚刚已经说了，那么队首的元素什么时候删除呢？由于我们只需要保存i的前k-1个元素中的最大值，所以当队首的元素的索引或下标小于 i-k+1的时候，就说明队首的元素对于求f(i)已经没有意义了，因为它已经不在窗里面了。所以当index[队首元素]＜i-k+1时，将队首
   元素删除。

从上面的介绍当中，我们知道，单调队列与队列唯一的不同就在于它不仅要保存元素的值，而且要保存元素的索引（当然在实际应用中我们可以只需要保存索引，而通过索引间接找到当前索引的值）。

为了让读者更明白一点，我举个简单的例子。

假设数列为：8，7，12，5，16，9，17，2，4，6.N=10,k=3.

那么我们构造一个长度为3的单调递减队列：

首先，那8和它的索引0放入队列中，我们用（8，0）表示，每一步插入元素时队列中的元素如下：

0：插入8，队列为：（8，0）

1：插入7，队列为：（8，0），（7，1）

2：插入12，队列为：（12，2）

3：插入5，队列为：（12，2），（5，3）

4：插入16，队列为：（16，4）

5：插入9，队列为：（16，4），（9，5）

。。。。依此类推

那么f(i)就是第i步时队列当中的首元素：8，8，12，12，16，16，。。。

一般来说，deque是STL总的双端队列容器，用deque可以很方便的实现单调队列

代码

单调队列:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt << 1
#define rson m + 1,r,rt << 1 | 1
#define rson m + 1,rt << 1 | 1
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int> pir;
const int N = 1e6 + 10;
deque<pir> q1; //维护最大值
deque<pir> q2; //维护最小值
int x,MIN[N],MAX[N];
int main()
{
    //freopen("in.txt","r",stdin);
    int n,k;
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&x);
        while (!q1.empty() && q1.back().first >= x) //队列递增
            q1.pop_back();
        q1.push_back(make_pair(x,i));
        if (i >= k)
        {
            while (!q1.empty() && q1.front().second <= i - k) //>的时候出去
                q1.pop_front();
            MIN[i] = q1.front().first;
        }
        while (!q2.empty() && q2.back().first <= x) //队列递减
            q2.pop_back();
        q2.push_back(make_pair(x,i));
        if (i >= k)
        {
            while (!q2.empty() && q2.front().second <= i - k)
                q2.pop_front();
            MAX[i] = q2.front().first;
        }
    }
    for (int i = k; i <= n; i++)
        printf("%d ",MIN[i]);
    puts("");
    for (int i = k; i <= n; i++)
        printf("%d ",MAX[i]);
    puts("");

    return 0;
}

set做法(poj过不了，scu可过)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a,rt << 1 | 1
#define inf 0x3f3f3f3f
typedef long long ll;
const int N = 1e6 + 10;
multiset<int> s;
int a[N],ans1[N],ans2[N];
int main()
{
   // freopen("in.txt",k;
    while (~scanf("%d%d",&k))
    {
        s.clear();
        for (int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            if (i <= k)
                s.insert(a[i]);
        }
        for (int i = 1; i <= n - k + 1; i++)
        {
            int j = i + k - 1;
            ans1[i] = *s.begin();
            ans2[i] = *s.rbegin();
            s.erase(s.find(a[i]));
            s.insert(a[j + 1]);
        }
        for (int i = 1; i <= n - k + 1; i++)
        {
            printf("%d ",ans1[i]);
        }
        printf("n");
        for (int i = 1; i <= n - k + 1; i++)
        {
            printf("%d ",ans2[i]);
        }
        printf("n");
    }
    return 0;
}

线段树:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <sstream>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
#define mem(a,rt << 1 | 1
#define inf 0x3f3f3f3f
typedef long long ll;
const int N = 1e6 + 10;
int ans1[N],ans2[N];
int MAX[N << 2],MIN[N << 2];
void pushup(int rt)
{
    MAX[rt] = max(MAX[rt << 1],MAX[rt << 1 | 1]);
    MIN[rt] = min(MIN[rt << 1],MIN[rt << 1 | 1]);
}
void build(int l,int r,int rt)
{
    if (l == r)
    {
        scanf("%d",&MAX[rt]);
        MIN[rt] = MAX[rt];
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int p,int add,int l,int rt)
{
    if (l == r)
    {
        MAX[rt] = add;
        MIN[rt] = add;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m)
        update(p,add,lson);
    else
        update(p,rson);
    pushup(rt);
}
int query_max(int L,int R,int rt)
{
    if (L <= l && r <= R)
        return MAX[rt];
    int m = (l + r) >> 1;
    int ans = -inf;
    if (L <= m)
        ans = max(ans,query_max(L,R,lson));
    if (R > m)
        ans = max(ans,rson));
    return ans;
}
int query_min(int L,int rt)
{
    if (L <= l && r <= R)
        return MIN[rt];
    int m = (l + r) >> 1;
    int ans = inf;
    if (L <= m)
        ans = min(ans,query_min(L,lson));
    if (R > m)
        ans = min(ans,rson));
    return ans;
}
int main()
{

    //freopen("in.txt",&k))
    {
        build(1,n,1);
        for (int i = 1; i <= n - k + 1; i++)
        {
            int j = i + k - 1;
            ans2[i] = query_max(i,j,1,1);
            ans1[i] = query_min(i,1);
        }
        for (int i = 1; i <= n - k + 1; i++)
            printf("%d ",ans1[i]);
        printf("n");
        for (int i = 1; i <= n - k + 1; i++)
            printf("%d ",ans2[i]);
        printf("n");
    }
    return 0;
}

（编辑：莱芜站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!