題目鏈接：http://www.lintcode.com/zh-cn/problem/sliding-window-maximum/#

滑動窗口的最大值

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

樣例

給出數組?[1,2,7,7,8], 滑動窗口大小為?k = 3. 返回?[7,7,8].

解釋：

最開始，窗口的狀態如下：

[|1, 2 ,7| ,7 , 8], 最大值為?7;

然后窗口向右移動一位：

[1, |2, 7, 7|, 8], 最大值為?7;

最后窗口再向右移動一位：

[1, 2, |7, 7, 8|], 最大值為?8.

挑戰

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

解決方案：

　　關于此題的理解， 為什么雙端隊列中插如的是數的索引，而不是數的本身？
因為如果是數的本身，我們就無法判斷窗口在移動的時候窗口里的數時候被移出窗口！

　　如果插入的是數的索引，那么該如何找出窗口中的最大值呢？
　　我們用雙端隊列維護一個隊首為大數索引，隊尾為小樹索引的隊列， 如果將要插入索引對應的數大于隊列末尾所對應的數，
那么隊列的末尾元素就被移出(此時將要插入的數和隊尾元素對應的數一定在同一窗口，既然將要插入索引對應的數大于隊列末尾所對應的數，那么隊列末尾所對應的數一定沒有機會成為窗口中的最大值);如果隊列中隊首值(窗口中元素最大數的索引) 不在新窗口的范圍里了，那么也要移出隊首元素。

vector<int> maxSlidingWindow(vector<int> &nums, int k) {deque<int> dq;vector<int> ret;int len = nums.size();for(int i=0; i<k; ++i){while(!dq.empty() && nums[i]>nums[dq.back()])dq.pop_back();dq.push_back(i);}for(int i=k; i<len; ++i){ret.push_back(nums[dq.front()]);while(!dq.empty() && nums[i]>nums[dq.back()])dq.pop_back();if(!dq.empty() && dq.front() <= i-k)dq.pop_front();dq.push_back(i);}ret.push_back(nums[dq.front()]);return ret; }

?

?

總結

以上是生活随笔為你收集整理的lintcode 滑动窗口的最大值(双端队列)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。