题目：

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[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]}。

思路：

最原始的思路是用个数据结构模拟，就用deque，然后最暴力的是扫描过来每一次都找最大值，这样复杂最高，优化一点可以分情况，若新加入的超过max，则无条件迭代他为max，若新加入的没有超过，则又分为旧max弹出和没弹出两种情况。只有在旧max弹出的时候要在deque里面从新扫描最大值。

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

//version1__16:34-17:29

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> v;
        if(size&&size<=num.size()){
            deque<int> wind;
            int max_elem=-9999, i=0;

            for(;i<size;++i){
                wind.push_back(num[i]);
                max_elem = max(max_elem, num[i]);
            }
            v.push_back(max_elem);
            for(;i<num.size();++i){
                int front = wind.front();
                wind.push_back(num[i]);
                wind.pop_front();
                if(wind.back() > max_elem){ //尾部插入和头部递增是必要的，然后就是看max的更新，若插入的比max还大，则直接就是新max也不管旧max是否被弹出，若插入的没有max大，则在此基础才判断max是否还在wind中
                    max_elem = wind.back(); //如在则要在wind中搜新的max，在则什么也不做
                }else{
                    if(front == max_elem){
                        max_elem = *max_element(wind.begin(), wind.end());
                    }
                }
                v.push_back(max_elem);
            }
        }
        return v;
    }
};

再用别人题解的思路也是这道题最精巧的思路：一个位置对应一个滑动窗（圈出的范围），在一个滑动窗宽度的数据中，最大值为基准，窗口右滑时若max还在窗口里且没有新的max比他更大，则max左端和右端的数据在窗口扫过的范围都是无效的，因为max已经比他们都大了，但又有区别，max坐标的数据是绝对不会用到了，右边的数据在窗口完全划出max时可能是成为新的max的（新增的数据都比旧数据小），所以：max左端是废弃数据，max有段是候选数据，在窗口滑出max时，右端从新找max而且接着的操作都一样，所以抽出来就是往右移动时右边的候选数据代替前边小的数据，维持数据成下降趋势的节点，这里不是存数据，而是存数据的下标。然后一开始是没有考虑窗口左边界，窗口越来越大，当有边界则每次右移后判断窗口左界，用窗口长度定出界后直接pop界外。

//17:29-19:13

class Solution2 {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> v;
        deque<int> wind;//里面存的是num的下标，不是num的值，因为会用到下标确定边界，同时有可以映射取出数值
        for(int i=0;i<num.size();++i){
            while(wind.size()&&num[wind.back()]<num[i]){//取值
                wind.pop_back();
            }
            wind.push_back(i);//下标
            if(i+1>=size){//要输出
                while (wind.size()&&wind.front()<((i+1)-size)){//下标,int型的deque wind.front取出int刚好可以和条件做判断，空取出0
                    wind.pop_front();                          //也可以改为if pop一次，只移动一个单位，或者最直接用外层判断，被临界条件0卡住，测试用例第一个就是0，导致溢出，自己没有样例又不知道
                }
                if(wind.size()){//这里也要单独判wind空，因为他的空是因为size导致整个流程失常：在wind有一个元素的时候会在上面那个循环pop掉导致下面没有，本来是不会到下面来的
                    v.push_back(num[wind.front()]);
                }
            }
        }
        return v;
    }
};

这里坑太多了，stl用的时候end要注意，front也要注意，同时容器为空时取出的数据也要注意（deque.front空取出0）。然后还有下标边界条件的坑，下标与数值混用，还有测试数据一开始就是用了个0的异常边界导致程序溢出测试样例又没有提示。。。超出边界程序倒是自动兼容了，但0的就很赋值的误差。