题解 | #滑动窗口的最大值#

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> temp;
        int index[100010];
        int wsize = size;
        if (size == 0 || size > num.size()) return temp;

        int hh = 0, tt = -1;
        for (int i = 0; i < num.size(); i ++)
        {
            if (hh <= tt && i - wsize + 1 > index[hh]) hh ++;
            cout << hh << ' ';
            while (hh <= tt && num[index[tt]] <= num[i]) tt --;
            index[ ++ tt] = i;
		  
            if (i - wsize + 1 >= 0)
            {
                temp.push_back(num[index[hh]]);
            }
        }
        return temp;
    }
};

通过index数组记录下标。index数组队头是最大值，这个下标数组包含了原数组降序排列的下标。所以队头是最大值，当窗口滑出，hh ++，原来第二大的值变成目前窗口内最大值。此时会有新元素加入窗口，因为index是降序，所以队尾是最小的，如果队尾没有新元素大，那么tt--，把它移出，循环会把目前队列中所有不比新元素大的值都移出。因为他们在不在队列里已经没有用了，新元素很大，说明直到窗口从刚框入新元素直到滑出新元素的范围内，新元素一直在，此时最大值一定不会是之前比新元素小的数字。

第一要在开始的时候判断窗口是否需要滑动，第二要在最后判断目前是否构成一个完整的窗口，然后才能输出。