147.栈与队列：滑动窗口最大值（力扣）

代码解决

class Solution {
private:
    class MyQueue
    {
    public:
        deque<int> que;

        // 删除队列中的元素，如果该元素等于队列的front
        // 这是为了保持队列中元素的正确性
        void pop(int val)
        {
            if(!que.empty() && val == que.front())
            {
                que.pop_front();
            }
        }

        // 添加元素到队列，同时维护队列中的元素是降序的
        // 通过移除所有小于当前值的元素，保证队列中的最大值在front位置
        void push(int val)
        {
            while(!que.empty() && val > que.back())
            {
                que.pop_back();
            }
            que.push_back(val);
        }

        // 获取队列的最大值（即队列的front）
        int front()
        {
            return que.front();
        }
    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        MyQueue que;
        vector<int> result;

        // 初始化前k个元素到队列
        for(int i = 0; i < k; i++)
        {
            que.push(nums[i]);
        }
        // 记录第一个窗口的最大值
        result.push_back(que.front());

        // 滑动窗口遍历后面的元素
        for(int i = k; i < nums.size(); i++)
        {
            // 移除窗口最左侧的元素
            que.pop(nums[i - k]);
            // 添加窗口最右侧的元素
            que.push(nums[i]);
            // 记录当前窗口的最大值
            result.push_back(que.front());
        }
        return result;
    }
};
deque<int> que:

使用双端队列来维护一个单调队列，队列中的元素是降序排列的。

void pop(int val):

如果队列不为空且要移除的值等于队列的前端值，则从队列中弹出该值。这一步是为了确保窗口的正确性。

void push(int val):

将新值 val 推入队列前，移除队列中所有小于 val 的元素。这保证了队列的降序性，因此队列的前端始终是最大值。

int front():

返回队列的前端值，这就是当前窗口的最大值。

maxSlidingWindow 方法

MyQueue que:

创建一个 MyQueue 实例来管理滑动窗口内的元素。

vector<int> result:

存储每个滑动窗口的最大值。

初始化前k个元素到队列:

将前 k 个元素推入 MyQueue 中。

result.push_back(que.front()):

记录第一个滑动窗口的最大值。

滑动窗口遍历后面的元素:

从第 k 个元素开始遍历到数组末尾：
移除窗口最左侧的元素。
添加窗口最右侧的元素。
记录当前窗口的最大值。