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;}
};

1. deque<int> que:

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

2. void pop(int val):

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

3. void push(int val):

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

4. int front():

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

maxSlidingWindow 方法

1. MyQueue que:

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

2. vector<int> result:

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

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

   • 将前 k 个元素推入 MyQueue 中。

4. result.push_back(que.front()):

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

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

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