poj2823(滑动窗口,单调队列模板)

2017年07月15日 11点热度 0人点赞 0条评论
Sliding Window
Time Limit: 12000MS   Memory Limit: 65536K
Total Submissions: 60659   Accepted: 17386
Case Time Limit: 5000MS

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

//维护滑动窗口的最大值和最小值,单调队列实现,因为每个数只出和进一次,所以时间复杂度是O(n)
/*
单调递减队列是这么一个队列,它的头元素一直是队列当中的最大值,
而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素,
可以从队列的两端删除元素。
1.首先看插入元素:为了保证队列的递减性,我们在插入元素v的时候,
要将队尾的元素和v比较,如果队尾的元素不大于v,则删除队尾的元素,
然后继续将新的队尾的元素与v比较,直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2.队尾的删除刚刚已经说了,那么队首的元素什么时候删除呢?
由于我们只需要保存i的前k-1个元素中的最大值,
所以当队首的元素的索引或下标小于i-k+1的时候,
就说明队首的元素对于求f(i)已经没有意义了,因为它已经不在窗里面了。
所以当index[队首元素]
#include
using namespace std;
const int mn=1e6+10;
int a[mn],q[mn],n,k;
void workmin()
{
    int l=1,r=0,i=0;
    for(; ia[i]) r--;
        q[++r]=i;
    }
    for(; ia[i]) r--;
        q[++r]=i;
        printf("%d ",a[q[l]]);
    }
    puts("");
}
void workmax()
{
    int l=1,r=0,i=0;
    for(; i

//这个代码莫名re了 
#include
#include
#include
using namespace std;
const int mn=1e6+10;
int a[mn],n,k;
map mi;
map > mx;
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
    	mi.clear();
    	mx.clear();
        for(int i=0; ifirst);
            mi.erase(mi.find(a[i-k+1]));
		}
		puts("");
		for(int i=k-1;ifirst);
            mx.erase(mx.find(a[i-k+1]));
		}
		puts("");
    }
    return 0;
}

未经允许不得转载!poj2823(滑动窗口,单调队列模板)

update

纸上得来终觉浅, 绝知此事须躬行。