| 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;
}
哈哈，今天收获还可以，还要努力哈~~~