首页 > 编程语言 >C++——单调队列

C++——单调队列

时间:2022-11-04 10:56:05浏览次数:51  
标签:队列 pop int que C++ front push 单调

class Solution {
public:
    class Myqueue       // 单调队列
    {
    public:
        deque<int>que;
        // 因为只维护了队列最大值,故在pop时判断滑动窗口最前方的值与最大值是否相等,相等则pop
        // 这样就保持了队列里的数值是单调从大到小的了。
        void pop(int value)
        {
            if(!que.empty() && value == que.front())
            {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int value)
        {
            while(!que.empty() && value > que.back())
            {
                que.pop_back();
            }
            que.push_back(value);
        }
        // 查询当前队列里最大值
        int front()
        {
            return que.front();
        }
    };

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        Myqueue que;
        vector<int>result;
        for(int i = 0; i < k; i++)  // 将前k个元素放进队列中
        {
            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;
    }
};

标签:队列,pop,int,que,C++,front,push,单调
From: https://www.cnblogs.com/dh2021/p/16856984.html

相关文章

  • 用队列结构,实现栈结构。(有图)
    packageclass03;importjava.util.LinkedList;importjava.util.Queue;importjava.util.Stack;/***用队列结构,实现栈结构*/publicclassCode07_TwoQueuesI......
  • C++ 获取时间戳
    获取unix时间戳std::time_tresult=std::time(nullptr);或者:constautop1=std::chrono::system_clock::now();std::cout<<"secondssinceepoch:......
  • c++11 unique_ptr
    unique_ptr使用详解      ......
  • C++静态成员和静态函数的正例和反例
      上图所示的代码都是正确的、并且能够按正常人的预期执行。首先提示一点、C++要用类名调用静态函数或者引用变量时、不是像Java一样用点号、而是用两个冒号! 错误......
  • C++中const修饰的成员函数
    const成员函数的格式:只要在函数后加上一个const就可以了TypeClassName::function(Typep)constintgetFoot(void)const{returnthis->foot; }https://blog.5......
  • C++17 The Complete Guide 电子书 pdf
    作者:[德]NicolaiM·Josuttis 链接:C++17TheCompleteGuide ......
  • C++——指针
    指针基本概念C++的指针也是标识符,不能与其它的普通变量重名;对指针的赋值操作通俗的被称为“指向某变量”,被指向的变量的数据类型称为“基类型”。指针占用的内存指针也......
  • C++Builder(BCB)学习群(QQ)
    点击链接加入群聊【C++Builder(BCB)学习群】:https://jq.qq.com/?_wv=1027&k=FHyDxiRw群名称:C++Builder(BCB)学习群群号:646968133......
  • C++ 通用的 toString() 函数
    1#include<iostream>2#include<string>34namespacestr_utils{56std::stringto_string(constchar*c_str){7std::cout<<"调用了......
  • c/c++访问lightdb
    /**src/test/examples/testlibpq3.c***testlibpq3.c*Testout-of-lineparametersandbinaryI/O.**Beforerunningthis,populateadatabase......