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

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& nums, int size) {
        // 单调队列，里面存的是数组下标。
        // 这个队列需要满足一个特性：队列前面的下标指向的元素一定比队列后面下标指向的元素要大。
        deque<int> max_elements;
        
        vector<int> ret;
        for (int i = 0; i < nums.size(); ++i)
        {
            // i这个下标应该放在哪里？
            // 直接从队列末尾开始扫，只要<=它，统统干掉
            while (!max_elements.empty() && (nums[max_elements.back()] <= nums[i]))
                max_elements.pop_back();
            
            // 放进i这个下标
            max_elements.push_back(i);
            
            // 队列前面的元素一定是最大的，所以理想状态下我们直接选最前面的就行
            // 但是这是个窗口，前面的元素可能已经不在这个窗口里面了，因此这里看看前面的元素还在不在，不在就删了
            while ((max_elements.front() + size) <= i)
                max_elements.pop_front();
            
            // 如果i满足形成窗口的条件，那么就把值送进返回数组
            if (i >= size - 1)
                ret.push_back(nums[max_elements.front()]);
        }
        return ret;
    }
};