首页 > 代码库 > POJ 2823 Sliding Window
POJ 2823 Sliding Window
Sliding Window
Time Limit: 12000MS | Memory Limit: 65536K | |
Total Submissions: 40956 | Accepted: 12150 | |
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.
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个数,给定k(k<=n),求依次从左到右所有长度为k的连续区间的最小值和最大值。
解析:由于n的范围已经给到了10^6,直接暴力的时间复杂度为O( (n-k)*k ),显然不能满足要求,所以今天我们要学一个神奇的队列——单调队列。
单调队列,其实只需要两个数组就能实现。一个p[ ]用来存队列中元素在原数组中的下标,a[ ]用来存元素的值。单调队列用来维护区间最值。
维护最大值:首先把第一个元素a[0]进到队列中,然后从剩下的n-1个中依次取出一个a[i]跟对尾的元素比较,将队尾比a[i]小的元素全部出队(因为比a[i]小的元素不可能是区间的最大值了),然后在队尾插入a[i],并记录q[rear] = i;这样我们就能得到最大值的队列了,但是所对应的元素有可能不在我们要求的区间范围内,那么我们就需要把队首的元素一次弹出,直到队首元素在所求范围内时,这时的队首元素就是该区间的最大值了。
维护最小值:其余的步骤都跟维护最大值一样,只是从队尾删除的是比当前元素大的元素,注意此时队首是区间的最小值。
AC代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; #define INF 0x7fffffff #define LL long long #define LLL(a, b) a<<b #define RRR(a, b) a>>b #define MID(a, b) a+(b-a)/2 const int maxn = 1000000 + 10; int q[maxn], a[maxn]; //q[]在原队列中的下标, a[]元素 int n, k; void solve(){ //维护区间最小值 int front = 0, rear = 0; //初始化 q[++rear] = 1; //先把第一个元素入队列 for(int i=1; i<=n; i++){ while(front <= rear && a[ q[rear] ] >= a[i]) rear --; q[++rear] = i; while(q[rear] - q[front] + 1 > k) front ++; if(i == k) printf("%d", a[ q[front] ]); if(i > k) printf(" %d", a[ q[front] ]); } puts(""); //维护区间最大值 front = 0, rear = 0; q[++rear] = 1; for(int i=1; i<=n; i++){ while(front <= rear && a[ q[rear] ] <= a[i]) //从队尾删除元素 rear --; q[++rear] = i; while(q[rear] - q[front] + 1 > k) //查找在区间中的值 front ++; if(i == k) printf("%d", a[ q[front] ]); if(i > k) printf(" %d", a[ q[front] ]); } puts(""); } int main(){ #ifdef sxk freopen("in.txt", "r", stdin); #endif // sxk while(scanf("%d%d", &n, &k)!=EOF){ memset(a, 0, sizeof(a)); for(int i=1; i<=n; i++) scanf("%d", &a[i]); solve(); } return 0; }
哈哈,今天收获还可以,还要努力哈~~~
POJ 2823 Sliding Window
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。