滑动窗口的最大值

　　滑动窗口：求数组内固定连续子区间的最大值。

/*
 *1. l..r为滑动窗口的左右边界，l永远小于r&&l和r只能扩不能缩---滑动窗口的两个硬性条件
 *2. 用双向链表实现,链表中的数据l-->r:max-->min
 * 尾端进：进的元素比队列中的元素大，队列中的元素出去，直到进的元素比队列中的元素小(进的是索引)
 * 头端出：出索引，索引过期
 */
#include <iostream>
#include <vector>
#include <list>
using namespace std;

class SlideWindow
{
public:
    const vector<int> slideWindow(const vector<int>& arr,const int size)
    {
        if(arr.size()<size||arr.empty())
            return arr;

        int len=arr.size();
        vector<int> res(len-size+1,0);
        list<int> l;//只保存在窗口划过数组时所有窗口的最大值
        for(int i=0,j=0;i<len;++i)
        {
            while(!l.empty()&&arr[l.back()]<=arr[i])
                l.pop_back();
            l.push_back(i);//下标入队

            if(i-l.front()==size)//观察队头元素是否过期
                l.pop_front();
            if(i>=size-1)
                res[j++]=arr[i];
        }
        return res;
    }
};
int main()
{
    SlideWindow sw;
    for(auto i:sw.slideWindow({4,3,5,4,3,3,6,7},3))
        cout<<i<<" ";
    cout<<endl;
    return 0;
}