題目描述
給定一個數組和滑動窗口的大小，找出所有滑動窗口里數值的最大值。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
解題思路
- 方案一：蠻力法，順序分塊掃描。例如在上例中，我們進行不斷的分組和查找，3個一組，這樣最終會找出其最大值。但是其時間復雜度為O(NK)。N為滑動窗口的數量，K為滑動窗口的大小。
- 方案二：雙端隊列實現。由于方案二中實現的步驟比較復雜，所以我們換了一種思路，在取得最大值的過程中，我們并不把每個數值都存入隊列，而只是把有可能成為最大值的數據存入到兩端開口的隊列(deque)中，上面的輸入為例，其求解過程如下：
代碼實現
class Solution {vector<int> res;deque<int> q;
public:vector<int> maxInWindows(const vector<int>& num, unsigned int size){if(num.size()>=size && size >= 1) //保證參數合理性{//取一個窗口中的最大值的下標for(int i=0;i<size;++i){if(!q.empty() && num[q.back()]<=num[i])q.pop_back();q.push_back(i);}//處理后面for(int i = size;i<num.size();++i){//每回將一個窗口中的最大值壓入結果集合//最大值永遠是以隊列頭元素為下標的值res.push_back(num[q.front()]);//如果后面元素大小有比以隊列中任何一個元素為下標的元素大的話//把隊列清空while(!q.empty() && num[q.back()] <= num[i])q.pop_back();//如果后面的元素沒有比當前最大元素大，但是窗口已經滿了，滑過了最大元素的下標if(!q.empty() && q.front() <= i-size)q.pop_front();q.push_back(i);}//最后一次循環結束，i到頭，最后一個窗口中的最大值就是//以隊列中頭元素為下標的值res.push_back(num[q.front()]);}return res;}
};
)
