力扣LCR184.设计自助结算系统

力扣LCR184.设计自助结算系统

• 一个队列存所有value

  • 一个数组模拟单调队列存区间最大值

•   const int N = 100010;
    int a[N];
    class Checkout {
        queue<int> q;
        int hh=0,tt=-1;
    public:
        Checkout() {
    
        }
        
        int get_max() {
            if(hh > tt) return -1;
            return a[hh];
        }
        
        void add(int value) {
            while(hh <= tt && a[tt] <= value) tt --;
            a[++tt] = value;
            q.push(value);
        }
        
        int remove() {
            if(q.empty())
                return -1;
            int ans = q.front();
            if(ans == a[hh])
                hh++;
            q.pop();
            return ans;
        }
    };