作者：翟天保Steven
版權(quán)聲明：著作權(quán)歸作者所有，商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處

題目描述：

給定一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 和滑動(dòng)窗口的大小 size ，找出所有滑動(dòng)窗口里數(shù)值的最大值。

例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[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]}。

數(shù)據(jù)范圍： 1≤size≤n≤10000，數(shù)組中每個(gè)元素的值滿足∣val∣≤10000

要求：空間復(fù)雜度 O(n)，時(shí)間復(fù)雜度 O(n)

示例：

輸入：

[2,3,4,2,6,2,5,1],3

返回值：

[4,4,6,6,6,5]

解題思路：

本題考察數(shù)據(jù)結(jié)構(gòu)隊(duì)列 & 棧的使用。本文采用雙向隊(duì)列的方式解題，即首尾均可以放入和彈出。

1）判斷窗口尺寸是否大于數(shù)組尺寸。

2）先確定首個(gè)窗口，此時(shí)隊(duì)列中首位是當(dāng)前窗口的最大值，因?yàn)楸仍撝蹈〉闹当粡棾隽?#xff0c;而后面更小的值則存放在隊(duì)列中。

3）以首個(gè)窗口的后一數(shù)值為起始，步進(jìn)遍歷。遍歷中執(zhí)行該步驟：存放隊(duì)列的首個(gè)數(shù)值至vector中，該值也是上個(gè)窗口的最大值；彈出當(dāng)前窗口外的數(shù)值；放入新的值，同時(shí)把隊(duì)列中比該值小的數(shù)值彈出。

4）這樣操作下來(lái)，隊(duì)列的首位始終是窗口的最大值，不用再執(zhí)行窗口的遍歷操作了。

測(cè)試代碼：

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        // 窗口大于數(shù)組長(zhǎng)度的時(shí)候，返回空
        if(size > num.size() || size == 0)
            return res;
        // 隊(duì)列
        deque <int> dq;  
        // 先確定首個(gè)窗口
        for(int i = 0; i < size; i++)
        {
            // 去掉比自己先進(jìn)隊(duì)列的小于自己的值
            while(!dq.empty() && num[dq.back()] < num[i]) 
                dq.pop_back();
            dq.push_back(i);
        }
        // 遍歷后續(xù)數(shù)組元素
        for(int i = size; i < num.size(); i++)
        {
            res.push_back(num[dq.front()]);
            // 彈出當(dāng)前窗口外的值
            while(!dq.empty() && dq.front() < (i - size + 1))
                dq.pop_front();  
            // 去掉比自己先進(jìn)隊(duì)列的小于自己的值
            while(!dq.empty() && num[dq.back()] < num[i])
                dq.pop_back();
            dq.push_back(i);
        }
        res.push_back(num[dq.front()]);
        return res;
    }
};

PS：該題目也可以用雙層遍歷的暴力破解法，只不過(guò)那樣復(fù)雜度就不是O(n)，而是O(mn)了，m是窗口尺寸，但是空間復(fù)雜度會(huì)降低至O(1)。