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

应该是最经典的hard题之一了。

基本思路：

• 一个重要的性质：如果滑动窗口右端在j时，滑动窗口内部有num[i] <= num[j]且i < j，那么其实在j以及j的右端，num[i]已经完全失去了作用（相当于被j覆盖了），可以被删除。
• 使用双端队列deque维护非递增序列，队头为滑动窗口最大值，向前移动添加元素时与队尾比较，把队尾所有小于该元素的元素全部删去再添加该元素；移除末位元素时仅需与队头比较，如果是队头则删除。

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        if (size == 0 || size > num.size()) return res;
        deque<int> dq;
        for (int i = 0; i < size; i++) {
            while (!dq.empty() && num[i] >= dq.back()) {
                dq.pop_back();
            }
            dq.push_back(num[i]);
        }
        res.push_back(dq.front());
        for (int i = size; i < num.size(); i++) {
            while (!dq.empty() && num[i] >= dq.back()) {
                dq.pop_back();
            }
            dq.push_back(num[i]);
            if (dq.front() == num[i - size]) dq.pop_front();
            res.push_back(dq.front());
        }
        return res;
    }
};