題目描述

給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數(shù)組{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]}。

解題思路

方案一：蠻力法，順序分塊掃描。例如在上例中，我們進(jìn)行不斷的分組和查找，3個一組，這樣最終會找出其最大值。但是其時(shí)間復(fù)雜度為O(NK)。N為滑動窗口的數(shù)量，K為滑動窗口的大小。

方案二：雙端隊(duì)列實(shí)現(xiàn)。由于方案二中實(shí)現(xiàn)的步驟比較復(fù)雜，所以我們換了一種思路，在取得最大值的過程中，我們并不把每個數(shù)值都存入隊(duì)列，而只是把有可能成為最大值的數(shù)據(jù)存入到兩端開口的隊(duì)列(deque)中，上面的輸入為例，其求解過程如下：

代碼實(shí)現(xiàn)

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) //保證參數(shù)合理性{//取一個窗口中的最大值的下標(biāo)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){//每回將一個窗口中的最大值壓入結(jié)果集合//最大值永遠(yuǎn)是以隊(duì)列頭元素為下標(biāo)的值res.push_back(num[q.front()]);//如果后面元素大小有比以隊(duì)列中任何一個元素為下標(biāo)的元素大的話//把隊(duì)列清空while(!q.empty() && num[q.back()] <= num[i])q.pop_back();//如果后面的元素沒有比當(dāng)前最大元素大，但是窗口已經(jīng)滿了，滑過了最大元素的下標(biāo)if(!q.empty() && q.front() <= i-size)q.pop_front();q.push_back(i);}//最后一次循環(huán)結(jié)束，i到頭，最后一個窗口中的最大值就是//以隊(duì)列中頭元素為下標(biāo)的值res.push_back(num[q.front()]);}return res;} };

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】_19 滑动窗口中的最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。