lintcode 滑動視窗的最大值(雙端隊列)

給出一個可能包含重複的整數數組，和一個大小為 k 的滑動視窗, 從左到右在數組中滑動這個視窗，找到數組中每個視窗内的最大值。

給出數組 <code>[1,2,7,7,8]</code>, 滑動視窗大小為 <code>k = 3</code>. 傳回 <code>[7,7,8]</code>.

解釋：

最開始，視窗的狀态如下：

<code>[|1, 2 ,7| ,7 , 8]</code>, 最大值為 <code>7</code>;

然後視窗向右移動一位：

<code>[1, |2, 7, 7|, 8]</code>, 最大值為 <code>7</code>;

最後視窗再向右移動一位：

<code>[1, 2, |7, 7, 8|]</code>, 最大值為 <code>8</code>.

O(n)時間，O(k)的額外空間

　　關于此題的了解， 為什麼雙端隊列中插如的是數的索引，而不是數的本身？

因為如果是數的本身，我們就無法判斷視窗在移動的時候視窗裡的數時候被移出視窗！

　　如果插入的是數的索引，那麼該如何找出視窗中的最大值呢？

　　我們用雙端隊列維護一個隊首為大數索引，隊尾為小樹索引的隊列， 如果将要插入索引對應的數大于隊列末尾所對應的數，

那麼隊列的末尾元素就被移出(此時将要插入的數和隊尾元素對應的數一定在同一視窗，既然将要插入索引對應的數大于隊列末尾所對應的數，那麼隊列末尾所對應的數一定沒有機會成為視窗中的最大值);如果隊列中隊首值(視窗中元素最大數的索引) 不在新視窗的範圍裡了，那麼也要移出隊首元素。