题解 | #滑动窗口的最大值#

class Solution {
public:

//方法一： 双向队列
vector<int> maxInWindows(const vector<int>& nums, int size) {

    vector<int> res;
    //窗口小于于数组长度才行
    if(size<=nums.size()&&size!=0)
    {
        deque<int> dq;  //双向队列
        for(int i=0;i<size;i++)
        {
            //去掉比自己先进队列的小于自己的值
            while(!dq.empty()&&nums[dq.back()]<nums[i])
            {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        //遍历后续数组元素
        for(int i=size;i<nums.size();i++)
        {
            res.push_back(nums[dq.front()]);
            while(!dq.empty()&&dq.front()<(i-size+1))
                dq.pop_front(); //弹出窗口移走后的值
            //加入新的值前，去掉比自己先进队列但比自己小的值
            while(!dq.empty()&&nums[i]>nums[dq.back()])
            {
                dq.pop_back();
            }
            dq.push_back(i);

        }

        res.push_back(nums[dq.front()]);
    }        
    return res;

}






/*
//方法二： 暴力法优化
vector<int> maxInWindows(const vector<int>& nums, int size) {

    vector<int> res(nums.size()-size+1);

    int index=-1;
    int max=-10001;

    for(int i=0;i<=nums.size()-size;i++)
    {
        if(index<i)  //情况一
        {
            max=-10001;
            for(int j=i;j<i+size;j++)
            {
                if(nums[j]>max)
                {
                    max=nums[j];
                    index=j;
                }
            }
        }
        else                //情况二
        {
            if(max<nums[i+size-1])
            {
                max=nums[i+size-1];
                index=i+size-1;
            }
        }
        res[i]=max;
    }

    return res;

}
*/

/*
//方法三：  暴力求解

vector maxInWindows(const vector& nums, int size) {

    vector<int> res(nums.size()-size+1);


    for(int i=0;i<=nums.size()-size;i++)
    {
        int max=nums[i];
        for(int j=i;j<i+size;j++)
        {
            if(nums[j]>max)
            {
                max=nums[j];
            }
        }
        res[i]=max;
    }

    return res;  
}
*/

};