题目
LCR 184. 设计自助结算系统 - 力扣（LeetCode）
请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：
get_max()：获取结算商品中的最高价格，如果队列为空，则返回 -1add(value)：将价格为value的商品加入待结算商品队列的尾部remove()：移除第一个待结算的商品价格，如果队列为空，则返回 -1
注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O(1)
示例 1：
输入:
["Checkout","add","add","get_max","remove","get_max"]
[[],[4],[7],[],[],[]]输出:
[null,null,null,7,4,7]示例 2：
输入:
["Checkout","remove","get_max"]
[[],[],[]]输出:
[null,-1,-1]提示：
1 <= get_max, add, remove 的总操作数 <= 100001 <= value <= 10^5
分析
为了实现较低的时间复杂度，不能每次获取最大值的时候，都去计算最大值，因此只能在构建数据的过程中就实时计算每次的最大值，并保存下来，这样的话需要获取最大值的时候只需要读取就能达到很快的速度。
而为了每次获取的时候都实时计算最大值，因此需要分析队列的数据构建方式。
首先队列是先进先出，后进后出的数据结构。
为了方便分析，分成两种情况去进行分析，分别是插入和释放的两种情况。
插入分析
现在先考虑插入场景，而暂时不考虑移除场景。
首先插入队列数据queue时候，维护一个最大值队列max。
queue 1
max 1随着数据的增加，明显，数据队列的最大值要跟随数据队列变化
当新增数据比之前数据大的时候，要做最大值合并。 最大值要始终覆盖成最大的，然后更新到最大值队列max中保存下来。
比如 先插入 1 2 3， 则最大值队列max中最大值是 3， 继续插入 4 5 ，则 最大值队列中的3 被依次替换成 4 ， 5， 最后是 5：
queue 1 2 3 4 5
max 5当新增数据比前面数据小的时候，最大值队列的数据不作变更， 而是以这次开始变小的数据为界限，再次统计最大值。至于为什么要再次统计，是因为当前面最大值数据被释放的时候（队列是先进先出），这个新增的最大值数据就是数据队列剩余值的最大值。
比如 继续依次插入 1 2 3 ， 则最大值队列max的值会依次变成 5 1， 5 2， 5 3， 最后是 5 3：
queue 1 2 3 4 5 1 2 3
max 5 3当插入的数据和最大值相等的时候，为了方便删除也需要将将这个数据插入最大值队列中。
queue 1 2 3 4 5 1 2 3 3
max 5 3 3当插入的数据总是比前面数据小的时候，不需要做最大值合并, 当插入数据比前面数据大的时候， 最大队列要始终进行合并直到和自身为最大为止。
比如数据队列继续插入 6 的时候， 6 总是比前面大，因此前面数据都被依次合并，最后最大值队列max的值变为6：
queue 1 2 3 4 5 1 2 3 3 6
max 6释放分析
现在再单独考虑释放的场景
使用 插入 6 之前的数据，数据如下：
queue 1 2 3 4 5 1 2 3 3
max 5 3 3释放数据队列queue中的数据的时候，只需要比较释放的数据是否为最大值队列max中的值即可，是的话最大值队列max面的值也一并释放, 当数据队列释放 1 … 5 的值时候，数据队列的值会变成 queue 1 2 3 3， 最大值队列前面的 5 被释放掉，剩余 3 3。 效果如下：
queue 1 2 3 3
max 3 3因为插入数据的时候，判断了插入值和最大值队列max尾部数据相同的时候也插入最大值队列中，因此当继续释放 1 2 3 的时候， 最大值队列也释放了一个 3 后，还会剩余一个3，结果还是能获取到数据队列queue的最大值，如下：
queue 3
max 3分析结论汇总
因此将规则汇总如下：
- 插入数据(尾插)时
- 如果插入queue的数据，从最大值队列max的后面往前面比较，总是比max前面的数据大，则从后往前递归合并最大值队列max的值，也就是删除小于插入数据的值。
- 如果插入queue的数据和最大值队列max尾部的数据相等，则也将这个数据插入最大值队列max中。
- 如果插入queue的数据小于最大值队列max尾部的数据，则也将这股数据插入最大值队列max中。
- 释放数据(头释)时，当释放的数据等于最大值队列max中的值，则最大值队列max也一起释放。
考虑到需要针对最大值队列max递归从后往前进行数据比较和释放，因此最大值队列max需要使用双向队列来进行存储。
代码
#include <queue>
#include <deque>
class Checkout {
public:
Checkout()
{
}
int get_max()
{
return m_q.empty() ? -1 : m_max.front();
}
void add(int value)
{
if (m_max.size() && value > m_max.back()) {
auto prev = m_max.end();
for (auto it = m_max.end() - 1; it != m_max.begin() - 1; --it) {
if (value > *it) {
prev = it;
}
}
if (prev != m_max.end())
m_max.erase(prev, m_max.end());
}
m_max.push_back(value);
m_q.push(value);
}
int remove()
{
if (m_q.empty())
return -1;
int val = m_q.front();
m_q.pop();
if (val == m_max.front()) {
m_max.pop_front();
}
return val;
}
private:
std::queue<int> m_q;
std::deque<int> m_max;
};
/**
* 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();
*/
#ifdef __TEST__
#include <iostream>
int main(int argc, char* argv[])
{
Checkout *c = new Checkout();
c->add(1);
c->add(2);
c->add(3);
std::cout << "max: 3 == " << c->get_max() << "\n";
c->add(4);
c->add(5);
std::cout << "max: 5 == " << c->get_max() << "\n";
c->add(1);
c->add(2);
c->add(3);
c->add(3);
std::cout << "max: 5 == " << c->get_max() << "\n";
c->remove();
c->remove();
c->remove();
c->remove();
std::cout << "max: 5 == " << c->get_max() << "\n";
c->remove();
std::cout << "max: 3 == " << c->get_max() << "\n";
c->remove();
std::cout << "max: 3 == " << c->get_max() << "\n";
c->add(6);
std::cout << "max: 6 == " << c->get_max() << "\n";
delete c;
return 0;
}
#endif //__TEST__