有一个整型数组 arr ，和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。
返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。
以数组为[4,3,5,4,3,3,6,7]，w=3为例。
第一个窗口[4,3,5]的最大值为5。
第二个窗口[3,5,4]的最大值为5。
第三个窗口[5,4,3]的最大值为5。
第四个窗口[4,3,3]的最大值为4。
第五个窗口[3,3,6]的最大值为6。
第六个窗口[3,6,7]的最大值为7。
最终返回[5,5,5,4,6,7]。
实现该解法的关键，是双端队列。
思路并不容易想，我们就直接说结论好了：
对数组进行遍历，遍历到第i个元素时，意味着该元素新加入到滑动窗口内。
双端队列是滑动窗口的一个子集，里面的元素保持从大到小排列。队列的内容是数组的下标。
对于新遍历的元素x：
- 队尾处理：
情况1：如果队列为空或x小于队尾指代的元素，则将x的下标加入到队尾
情况2：如果不满足情况1，从队列尾部弹出元素，直至满足情况1为止。 - 队头处理：
如果队列的头部和尾部差值大于等于m(窗口长度超过m)，则弹出队头。
至此，队头元素指代的数值就是当前窗口最大值。
CODE
void slide(const vector<int>&arr,const int m,vector<int>&res){
int n=arr.size();
if(arr.empty()||m>n)
return;
//用于存储，每个元素加入窗口时，窗口的最大值
vector<int> out(n);
deque<int> win;
for(int i=0;i<n;++i){
while(!win.empty()&&arr[win.back()]<arr[i]){
win.pop_back();
}
win.push_back(i);
if(win.back()-win.front()>=m)
win.pop_front();
out[i]=arr[win.front()];
}
//最后题目要求的和out数组差了前面几个元素
res.resize(n-m+1);
for(int i=m-1;i<n;++i)
res[i-m+1]=out[i];
}
这样的话，每个元素只进入队列一次，出一次，所以时间代价：O(N)
TIP：谈谈数组的传入传出
- 使用指针
- 传入：数组头
int*加上长度N或begin end指针 - 传出：
- 用new分配数组,然后return该指针（风险:内存泄漏）
- 利用参数传入指针（风险：需保证指针后有足够空间，否则会越界）
- 或者return的指针本身就是传入参数指针或者移位后的指针，但是不多见。（风险：同上）
- 利用vector
- 传入传出：参数传递加引用，节约空间和时间
- 往往不用return来传出，来避免拷贝。
- 易错点：访问越界。
当vector传入函数时，其空间可能很有限或者为空。
Tip：可以用resize来指定大小。
