栈思想

• 和含有min函数的栈那像：保存极值，当极值更新为新的数字或者追溯到上一个极值，追溯+时间O(n) 意味着不能遍历，每次移动都要保存当前情况下的极值。
• 窗口移动时，如果过期元素恰好为极值，那么重新寻找，不然新元素只需要和v的尾部元素比较，尾部元素代表i~i+size-2的最大值。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> v;
        if(size>num.size()||!size)
        {
            return v;
        }
        for(int i=0;i+size<=num.size();i++)
        {
             if(i==0||v[v.size()-1]==num[i-1])
             {
                //重新找最大值
                int j=0;
                int m=0;
                while(j<size)
                {
                    m=max(m,num[j+i]);
                    j++;
                }
                //最大值
                v.push_back(m);
             }
             else{
                if(v[v.size()-1]<num[i+size-1])
                {
                    //新的值是最大值
                    v.push_back(num[i+size-1]);

                }
                else{
                    v.push_back(v[v.size()-1]);
                }
             }
        }
        return v;
    }
};

单调队列

• 构造单调队列，双头队列可以从前后删除特性使得保存次极值和次次极值等，不需要像数组或者栈一样遍历重新寻找
• 边界情况在i>size-1时，此时极值才符合窗口。以及过期索引问题

#include <deque>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> v;
        if(num.empty()||size==0||size>num.size())
        {
            return v;
        }
        deque<int> dq;
        for(int i=0;i<num.size();i++)
        {
            while(!dq.empty()&&num[dq.back()]<num[i])
            {
                dq.pop_back();
            }
            dq.push_back(i);
            if(dq.front()+size<=i)
            {
                dq.pop_front();
            }
            if(i>=size-1)
            {
                v.push_back(num[dq.front()]);
            }
        }
        return v;
    }
};