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

方法1：暴力
这个方法还是挺好理解的，就是对于每个滑动窗口，我们来进行最大值的查找即可
时间复杂度：因为对于每个起点我们都遍历过一遍滑动窗口的大小，所以是O()
空间复杂度：O(n)

————
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;//答案数组
        for (int i = 0; i < num.size(); i ++ ) {
            int l = i, r = i + size - 1;//列出起点和终点
            if (r >= num.size()) break;//如果窗口大了，返回空
            int mx = 0;
            //找窗口内最大值
            for (int j = l; j <= r; j ++ ) mx = max(mx, num[j]);
            res.push_back(mx);
        }
        return res;
    }
};

方法2：单调队列
所谓单调队列，就是队列中的元素都是单调的
那么我们如何用单调队列来做这题呢，我们用样例来模拟一遍
当队列内为空的时候，将当前元素从队尾插入

继续看下一个元素，其大于队尾元素，说明有3的存在，那么最大值一定不是2，况且2在3的前面，会更早的被弹出队列， 所以将2弹出，放3

下一个元素同理

我们发现下一个元素比队尾小，于是插入队尾

我们发现下一个元素比队尾小，于是一直弹出队尾，到小于队尾元素或者队列为空为止，然后加入到队列中

接下来依次类推



我们注意到，队列中的元素是呈单调下降的，所以每次滑动窗口的队头就是滑动窗口的最大值
所以我们每次插入元素前，还要检查队头是否还在滑动窗口内
时间复杂度：由于我们只遍历了每个元素一遍所以是O(n)
空间复杂度：存储数组O(n)

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> q(num.size() + 1);//用数组来模拟单调队列，为了方便检查对头是否跳出滑动窗口，单调队列中存储的是元素的下标
        vector<int> res;//存储答案
        int hh = 0, tt = -1;//这里是队头队尾
        int n = num.size();
        for (int i = 0; i < n; i ++ ) {
            if (hh <= tt && q[hh] <= i - (int)size) hh ++;//检查队头是否合法
            while (hh <= tt && num[i] >= num[q[tt]]) tt --;//检查队尾是否比当前值小
            q[++ tt] = i;
            if (i >= size - 1) res.push_back(num[q[hh]]);//如果滑动窗口小于等于数组长度的时候记录答案，最大值就是队头元素
        }
        return res;
    }
};