本文主要是介绍LCR 184.设计自助结算系统，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路分析:
这个题,我们需要单调队列来维护当前的最大值,达到O(1)的时间复杂度,同时使用一个数组记录当前出现的元素
get_max就返回队头即可, add就在加入之前删除掉所有小于他的元素即可,等于的元素应该放在不删除.不然就会提前出现-1
而remove会比较有趣,他每次是返回数组的当前元素,而且如果这个元素等于队头,那么说明单调队列要pop_front(), 而且dq里面的元素是vector里面的元素的子序列,所以每次删除一定是正确的
代码如下:
class Checkout {
public:deque<int> dq;vector<int> v;int count=0;Checkout() {}int get_max() {if(!v.empty() && count<v.size()){return dq.front();}else{return -1;}}void add(int value) {v.push_back(value);while(!dq.empty() && value>dq.back()){dq.pop_back();}dq.push_back(value);}int remove() {if(!v.empty() && count<v.size()){if(v[count]==dq.front()) dq.pop_front();//dq里面的元素也都是按照 add(val)的顺序排列的//v 里面的元素也都是按照 add(val)的顺序排列的//而且dq里面的元素 是 v里面元素的子集 //所以dq一定会被正确popreturn v[count++];}else return -1;}
};/*** Your Checkout object will be instantiated and called as such:* Checkout* obj = new Checkout();* int param_1 = obj->get_max();* obj->add(value);* int param_3 = obj->remove();*/这篇关于LCR 184.设计自助结算系统的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
