LCR 184. 设计自助结算系统 - 力扣(LeetCode)
总结:利用一个双端维护队列一个往后递减的队列,对头是最大值,每次进入一个新值时就一直和队尾元素比较将比新的值小的数排出,这样能保证留在队列中的数都是会对最大值产生影响的数,而当主队列中将要排出的数与双端队列对头数相等时则也要将双端队列队头数排出,否则会对主队列中最大的数产生影响。文章来源:https://www.toymoban.com/news/detail-731012.html
代码:文章来源地址https://www.toymoban.com/news/detail-731012.html
class Checkout {
queue<int> que;
deque<int> 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;
}
};
到了这里,关于算法练习第六十四天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!