大家好，我是梁唐。

最近在劍指offer里看到一道算法題很有意思，分享給大家。

題面很簡單，只有一句話，叫做對(duì)一維數(shù)組做maxpooling。

可能很多同學(xué)不知道pooling是什么意思，pooling是深度學(xué)習(xí)中的一個(gè)術(shù)語，翻譯過來叫做池化。池化的目的是壓縮張量的規(guī)模，張量可以理解成是矩陣。

池化的時(shí)候會(huì)將一個(gè)小窗口在矩陣上移動(dòng)，每次會(huì)對(duì)小窗口內(nèi)的元素進(jìn)行計(jì)算，得到一個(gè)值。不同的池化方法體現(xiàn)在這里的計(jì)算的方式不同，比如常見的maxpooling，指的是每次從窗口中找出最大值的操作，再比如常見的sumpooling，則是進(jìn)行求和計(jì)算。

我們可以看下下圖，就是一個(gè)典型的maxpooling的操作。

池化的時(shí)候，窗口的大小是2x2，移動(dòng)的步長是2，每次都取出這2x2個(gè)數(shù)中的最大值，因此叫做最大值池化，英文就是maxpooling。

很明顯經(jīng)過池化之后，矩陣的大小大大壓縮了，如果使用2x2的規(guī)模進(jìn)行池化，得到的結(jié)果是原本的1/4。一般在卷積神經(jīng)網(wǎng)絡(luò)當(dāng)中，由于原始的輸入規(guī)模比較大(圖片或者是視頻)，所以會(huì)反復(fù)進(jìn)行池化，將原始的張量反復(fù)壓縮，提取出最核心的特征點(diǎn)。

那如果是一維的池化怎么操作呢，其實(shí)是一樣的，只不過窗口也換成了一維的而已。

比如說我們有這樣一個(gè)數(shù)組：[12, 20, 30, 0]，窗口大小是2，步長是1，那么池化得到的結(jié)果是[20, 30, 30]。

介紹完了pooling的概念之后，我們?cè)倩氐筋}目本身：給定一個(gè)長度為n的數(shù)組，再給定一個(gè)整數(shù)k，要求以k為窗口長度步長為1進(jìn)行maxplooing之后的結(jié)果。

由于步長為1，所以我們一共要求n-k+1個(gè)最大整數(shù)，每次求最大整數(shù)如果采用遍歷的話，需要遍歷k個(gè)元素。那么整體就是，極端情況下，比如k=n/2時(shí)，問題的復(fù)雜度為。

這個(gè)只是暴力求解的方法，顯然在面試的時(shí)候這樣的答案是無法讓面試官滿意的，我們必須要想出更快的方法來。

我們簡單分析一下問題會(huì)發(fā)現(xiàn)，如果我們把窗口滑動(dòng)看成是一次求解區(qū)間最大值的操作，那么這樣的操作數(shù)是固定的，也就是n-k+1，這個(gè)數(shù)字是固定的，是我們無法改變的。所以如果想要優(yōu)化復(fù)雜度的話，只能從另外一個(gè)維度，也就是每次求解時(shí)的計(jì)算復(fù)雜度入手。

在暴力的方法下，我們每次遍歷k個(gè)元素，找到最大值。稍微分析一下就會(huì)發(fā)現(xiàn)，這里面有大量的重復(fù)。因?yàn)榇翱诘牟介L為1，假設(shè)某一次窗口內(nèi)的元素是，移動(dòng)之后的元素就是，當(dāng)中有k-1個(gè)元素是重復(fù)的。

不難看出，對(duì)于每個(gè)元素來說，它最多會(huì)在k個(gè)窗口當(dāng)中出現(xiàn)。對(duì)于每一個(gè)窗口我們都遍歷了一次，其實(shí)是沒有必要的，這當(dāng)中存在大量的冗余。所以我們要做的就是想辦法優(yōu)化它，盡量讓每個(gè)元素只會(huì)遍歷一次，或者是遍歷常數(shù)次。

你看，雖然我們現(xiàn)在還是沒有想出解法，但是我們通過分析問題，已經(jīng)找到了方向，正在一步步逼近答案。

順著這個(gè)思路我們可以想到，我們可以維護(hù)上一個(gè)區(qū)間的最大值，我們假設(shè)這個(gè)最大值是m，然后和當(dāng)前區(qū)間新加入的元素進(jìn)行對(duì)比，大的那個(gè)就是當(dāng)前區(qū)間的答案。

思路上看起來貌似可以，但細(xì)節(jié)上有一些問題。首先，上一個(gè)區(qū)間的最大值是可能會(huì)過期的。比如上一個(gè)區(qū)間剛好第一個(gè)元素最大，而當(dāng)前區(qū)間第一個(gè)元素是，并不在當(dāng)前區(qū)間里，所以是不能作為答案的。

我們是可以很容易判斷上一個(gè)區(qū)間的最大值有沒有過期的，但問題在于如果這個(gè)答案過期了，我們就抓瞎了，不知道哪個(gè)值是答案了。

那要怎么解決呢?

其實(shí)也很簡單，我們維護(hù)一個(gè)最大值會(huì)存在過期的問題，那干脆我們維護(hù)多個(gè)最大值嘛，我們維護(hù)多個(gè)答案，即使剛好因?yàn)閰^(qū)間移動(dòng)有一個(gè)最大值過期了，還有第二個(gè)能夠頂上，這樣不就OK了嗎?

的確，這樣就搞定了，整個(gè)思路基本上就貫穿了。剩下的問題就是多個(gè)最大值如何維護(hù)的問題了，由于要維護(hù)多個(gè)值，我們自然需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)，只用幾個(gè)變量是不行的了。

對(duì)于這個(gè)數(shù)據(jù)來說，我們讀到了新的數(shù)據(jù)時(shí)要很方便插入，對(duì)于之前過期的答案我們也要很方便移除，同時(shí)還要保證運(yùn)行效率。在這幾個(gè)要求的結(jié)合之下，只剩下雙端隊(duì)列這一個(gè)選項(xiàng)了。

能想到雙端隊(duì)列，基本上這題就做出一大半了。

剩下的問題就是怎么使用它，由于我們的目的是找到最大值，并且是盡量快地找到合適的最大值，比較容易想到我們可以將雙端隊(duì)列設(shè)計(jì)成有序的。我們每次從最大值開始判斷，如果它還在窗口內(nèi)，就是答案，如果已經(jīng)超出了，就將它拋棄判斷第二大，循環(huán)往復(fù)直到找到答案。

最后還剩下兩個(gè)小問題，第一個(gè)小問題是我們?cè)趺磁袛嘧畲笾凳欠襁^期?

很簡單，我們?cè)诖鎯?chǔ)的時(shí)候可以不用存元素的值，而存元素的下標(biāo)。通過下標(biāo)就可以很輕易判斷它是否在窗口內(nèi)，如果不在，那么自然說明已經(jīng)過期了。

第二個(gè)問題是，每次移動(dòng)窗口之后讀入新的值如何更新?這也很簡單，我們可以從末尾開始替換掉雙端隊(duì)列中比它小的元素。這樣既更新了隊(duì)列，又保證了隊(duì)列的有序性。

閑言少敘，我們直接來看代碼：

voidget_max_pooling(intn,intk,vector<int>&nums,vector<int>&ans){
deque<int>dque;
//讀入前k個(gè)元素
for(inti=0;i-1;i++){
intu=nums[i];
//從隊(duì)列右側(cè)插入，替換掉比它小的元素，保證有序性
while(!dque.empty()&&u>nums[dque.back()]){
dque.pop_back();
}
//插入元素的下標(biāo)而非具體的值
dque.push_back(i);
}
for(inti=k-1;iintu=nums[i];
//更新隊(duì)列，操作同上
while(!dque.empty()&&i-dque.front()>=k){
dque.pop_front();
}
//從隊(duì)首拿到第一個(gè)在窗口內(nèi)的元素
while(!dque.empty()&&(u>nums[dque.back()]||i-dque.back()>=k)){
dque.pop_back();
}
dque.push_back(i);
ans.push_back(nums[dque.front()]);
}
}

從代碼來看，這題的代碼量并不大，實(shí)現(xiàn)起來也并不復(fù)雜，但勝在思路巧妙。也算是劍指offer當(dāng)中一道非常經(jīng)典出鏡率很高的題。

如果大家看不明白，可以結(jié)合一下代碼再回過頭去看下算法推導(dǎo)的過程。算法勝在思路而非答案。

好了，關(guān)于這道題就先聊到這里，祝大家日拱一卒。

原文標(biāo)題：劍指算法題，一維數(shù)組求maxpooling

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

審核編輯：湯梓紅