银川网站建设广告公司名单,科技助手,北京房产网最新楼盘,wordpress v2ex 设计链接#xff1a;
剑指 Offer 59 - II. 队列的最大值
题意#xff1a;
如题#xff0c;要求O1给出数列的最大值
解#xff1a;
类似滑动窗口
1 1 2 1 2用双端队列存储成2 2#xff08;每次从前面获取最大值#xff0c;后面插入新数字#xff09;也就是第一个2覆盖了…链接
剑指 Offer 59 - II. 队列的最大值
题意
如题要求O1给出数列的最大值
解
类似滑动窗口
1 1 2 1 2用双端队列存储成2 2每次从前面获取最大值后面插入新数字也就是第一个2覆盖了前面两个1第二个2覆盖了一个1
1 1 2 3 2存储成3 2因为在抛弃到3之前3都是队列内最大的移除前面的和最大值3无关直到移除3
核心思想越后面进入队列的数字存在时间越久存在久的数字可以替换小于它的存在短的数字移除最大数字前面的数字对最大值没有影响直到移除最大的数字以后更新成次大数
实际代码
#includebits/stdc.h
using namespace std;
class MaxQueue
{
public:MaxQueue() default;//默认构造 int max_value(){if(Max.empty()) return -1;else return Max.front();}//获取最大值 void push_back(int value){qe.push(value);while(!Max.empty() valueMax.back()) Max.pop_back();Max.push_back(value);}//压入队列 int pop_front(){if(qe.empty()) return -1;int retqe.front();qe.pop();if(retMax.front()) Max.pop_front();return ret;}//抛出队列
private:queueintqe;dequeintMax;
};
int main()
{}限制
1 push_back,pop_front,max_value的总操作数 100001 value 10^5
