当前位置: 首页> 游戏> 手游 > 147.栈与队列:滑动窗口最大值(力扣)

147.栈与队列:滑动窗口最大值(力扣)

时间:2025/7/10 18:18:11来源:https://blog.csdn.net/weixin_63779802/article/details/139236158 浏览次数:0次

代码解决

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 个元素开始遍历到数组末尾:
      • 移除窗口最左侧的元素。
      • 添加窗口最右侧的元素。
      • 记录当前窗口的最大值。
关键字:147.栈与队列:滑动窗口最大值(力扣)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: