程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 2823 Sliding Window

POJ 2823 Sliding Window

編輯：關於C++

Sliding Window
Time Limit: 12000MS Memory Limit: 65536K Total Submissions: 40956 Accepted: 12150 Case Time Limit: 5000MS

Description

An array of size n ≤ 10⁶ 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個數，給定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 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x7fffffff
#define LL long long
#define LLL(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;
}