做神马网站优,证件照制作免费版,手机端网页设计规范,优科技网站建设LCR 184. 设计自助结算系统 - 力扣#xff08;LeetCode#xff09;
总结#xff1a;利用一个双端维护队列一个往后递减的队列#xff0c;对头是最大值#xff0c;每次进入一个新值时就一直和队尾元素比较将比新的值小的数排出#xff0c;这样能保证留在队列中的数都是会…LCR 184. 设计自助结算系统 - 力扣LeetCode
总结利用一个双端维护队列一个往后递减的队列对头是最大值每次进入一个新值时就一直和队尾元素比较将比新的值小的数排出这样能保证留在队列中的数都是会对最大值产生影响的数而当主队列中将要排出的数与双端队列对头数相等时则也要将双端队列队头数排出否则会对主队列中最大的数产生影响。
代码
class Checkout {queueint que;dequeint d;public:Checkout() {}int get_max() {if(d.empty()){return -1;}return d.front();}void add(int value) {while(!d.empty() value d.back()){d.pop_back();}d.push_back(value);que.push(value);}int remove() {if(que.empty()){return -1;}int temp que.front();if(temp d.front())d.pop_front();que.pop();return temp;}
};
