滑动窗口最大值

题意:

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位

分析:

在处理滑动窗口最大值的问题时，暴力方法的时间复杂度为 O(n⋅k)，会在大数据规模下超时。为了提高效率，可以使用单调队列。

单调队列的优势
单调队列是一种在滑动窗口中用于高效查找最大值或最小值的数据结构。它保持队列内元素的递减顺序，从而确保可以在  
O(1) 时间内获取当前窗口的最大值。

单调队列的核心逻辑
保持单调性：队列内的索引按值递减，确保队列前端始终是当前窗口的最大值。
滑动窗口更新：每次滑动窗口时，通过添加新元素和移除超出窗口的元素来维护队列的单调性。

Code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& a, int k) {
        vector<int> ans;     
        int n = a.size();  
        deque<int> dq;      
        for (int i = 0; i < n; i++) { 
            while (!dq.empty() && a[i] >= a[dq.back()]) { // 当队列不为空且当前元素大于等于队列中最后一个元素的值时，弹出队列尾部的索引
                dq.pop_back();
            } 
            dq.push_back(i); // 将当前元素的索引加入队列
            if (i - dq.front() >= k) { // 如果队列的最前面索引超出了滑动窗口的范围，弹出队列前端的索引
                dq.pop_front();
            } 
            if (i + 1 >= k) { // 当滑动窗口大小达到k时，将队列前端的元素对应的值加入结果数组
                ans.push_back(a[dq.front()]);
            }
        } 
        return ans;  
    }
};