第三十三题 队列和栈第五题
方法一：暴力破解 直接在遍历每个窗口中所有的值 找最大值
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> ret_ans;
        // 直接暴力运算 每次找最大值保存进去
        if(num.size()<size || size==0)
            return ret_ans;
        
        // 第一层循环 决定窗口的起始位置
        for(int i =0;i<num.size()-size+1;i++)
        {
            int max=-1;
            // 循环遍历窗口内的每一个值
            for(int j =0;j<size;j++)
            {
                if(num[i+j]>max)
                    max=num[i+j];
            }
            // 存入最大的值
            ret_ans.push_back(max);
        }
        
        return ret_ans;
    }
};

方法二：之前的窗口的最大值是可以利用的
假设序列是 2,3,4,2,2,6,5,1 窗口为4
[ 2 3 4 2 ] 2 6 5 1    max=4
2 [ 3 4 2 2 ] 6 5 1    之前2342的max保存下来了，只要而淘汰的只是2，所以342的最大值还是4，只要用4和新来的2比较既可 得到max = 4
2 3 [ 4 2 2 6 ] 5 1    之前3422的max保存了，4还在，只要比较新来的6和4即可    max=6
.......

还有一种情况就是
序列 10 3 2 1 5 6 7 8 ... 窗口是3
[ 10 3 2 ] 1 5 6 7 8    第一次 max=10
10 [ 3 2 1 ] 5 6 7 8    因为max的10被删掉了，所以 应该全部重新找 max=3
10 3 [ 2 1 5 ] 6 7 8    因为3 被删掉了应该全部重新找 max=5
......

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> ret_ans;
        // 方法二 不用每次在窗口找最大值
        // 因为之前就已经找到了窗口内的最大值 如果说 删掉的是前一次窗口的最大值，那么需要重新遍历
        // 但是如果删除的不是之前一个窗口的最大值，那就不需要重新遍历 只需要将最大值和最新加进来的值比较谁大 就可
        // 直接暴力运算 每次找最大值保存进去
        if(num.size()<size || size==0)
            return ret_ans;
        
        int max=-1;
        // 第一层循环 决定窗口的起始位置
        for(int i =0;i<num.size()-size+1;i++)
        {
            // 如果说 上一个窗口的最大值已经被删掉了 那么需要重新遍历找最大值
            // i==0 表示第一次进来 此时肯定要循环
            if(num[i-1] == max || i ==0){
                max=-1;
                // 循环遍历窗口内的每一个值
                for(int j =0;j<size;j++){
                    if(num[i+j]>max)
                        max=num[i+j];
                }
            }
            // 如果上一个窗口的最大值没有被删掉，只要比较最新加进来的值和之前的最大值 谁大就好
            else{
                if(max<num[i+size-1])
                    max=num[i+size-1];
            }
            // 存入最大的值
            ret_ans.push_back(max);
        }
        
        return ret_ans;
    }
};