poj 2823 Sliding Window單調隊列

這道題的意思是給定一個長N的整數序列，用一個大小為K的窗口從頭開始覆蓋，問第1-第N-K次窗口裡面最大的數字和最小的數字。
   剛開始還以為優先級隊列可以做，發現無法刪除最前面的元素。估計用線段樹這個題也是可以解得。用這個題學了下單調隊列。
  
   單調隊列正如其名，是一個從小到大排序的隊列，而且能夠保證所有的元素入隊列一次出隊列一次，所以平攤到每個元素的復雜度
就是O(1)。
   對於這個題單調隊列的使用。以序列1 3 -1 -3 5 3 6 7舉例。
   1）元素類型：一個結構體，包含數字大小和位置，比如(1，1），（3，2）。
   2）插入操作：從隊尾開始查找，把隊尾小於待插入元素的元素全部刪除，再加入待插入的元素。這個操作最壞的
情況下是O(n)，但是我們采用聚集分析的方法，知道每個元素最多刪除一次，那麼N個元素刪除N次，平攤到每一次
操作的復雜度就是O(1)了。
   3）刪除隊首元素：比如本文給的那個題，窗口一直往後移動，每一次移動都會刪除一個元素，所以很可能隊首會是要
刪除的元素，那麼每次移動窗口的元素要進行一次檢查，如果隊首元素失效的話，就刪掉隊首元素。

   代碼的實現，我是包裝deque實現了一個模版類。速度很不好，居然跑了11s多才過，幸虧給了12s的時間，看status又500多ms
就過了的。估計數組實現會快很多。

   代碼如下：
#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
#define MAX_N (1000000 + 100)
int nNum[MAX_N];
int nN, nK;

struct Small
{
    int nValue;
    int nIndex;
    Small(int nV, int index):nValue(nV), nIndex(index) {}
    bool operator < (const Small& a) const
    {
        return nValue < a.nValue;
    }
};

struct Big
{
    int nValue;
    int nIndex;
    Big(int nV, int index):nValue(nV), nIndex(index) {}
    bool operator < (const Big& a) const
    {
        return nValue > a.nValue;
    }
};

//單調隊列
template <typename T> class Monoque
{
    deque<T> dn;

public:
    void Insert(T node)
    {
        int nPos = dn.size() - 1;
        while (nPos >=0 && node < dn[nPos])
        {
            --nPos;
            dn.pop_back();
        }
        dn.push_back(node);
    }

    int Top()
    {
        return dn.front().nValue;
    }

    void Del(int nBeg, int nEnd)
    {
        if (dn.size() > 0)
        {
            if (dn.front().nIndex < nBeg || dn.front().nIndex > nEnd)
            {
                dn.pop_front();
            }
        }
    }
};

int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        int i;
        for (i = 0; i < nN; ++i)
        {
            scanf("%d", &nNum[i]);
        }
        Monoque<Small> minQ;
        Monoque<Big> maxQ;

        for (i = 0; i < nK; ++i)
        {
            minQ.Insert(Small(nNum[i], i));
        }

        for (i = 0; i < nN - nK; ++i)
        {
            printf("%d ", minQ.Top());
            minQ.Insert(Small(nNum[i + nK], i + nK));
            minQ.Del(i + 1, i + nK);
        }   www.2cto.com
        printf("%d\n", minQ.Top());

        for (i = 0; i < nK; ++i)
        {
            maxQ.Insert(Big(nNum[i], i));
        }

        for (i = 0; i < nN - nK; ++i)
        {
            printf("%d ", maxQ.Top());
            maxQ.Insert(Big(nNum[i + nK], i + nK));
            maxQ.Del(i + 1, i + nK);
        }
        printf("%d\n", maxQ.Top());
    }

    return 0;
}