劍指 Offer 59 - II. 隊列的最大值

使用一個queue和一個deque，queue進行正常的push和pop操作，deque輔助找到當前隊列中最大值

入隊時，如果當前元素value小於deque隊尾元素，直接把value入隊deque；如果當前元素value大於deque隊尾元素，從deque隊尾開始，把小於value的元素全部從隊尾出隊。（deque內元素是降序的）

出隊時，只要queue隊首元素小於deque隊首元素，直接出隊queue隊首元素即可；若queue隊首元素和deque隊首元素相等了，則兩者一起出隊。deque隊首元素錶示的是，queue不把該值出隊，deque隊首元素都是最大的

class MaxQueue {
    
public:
    queue<int> q;
    deque<int> deq;

    MaxQueue() {
    

    }
    
    int max_value() {
    
        if(q.empty()){
    
            return -1;
        }
        return deq.front();
    }
    
    void push_back(int value) {
    
        while(!deq.empty() && value > deq.back()){
    
            deq.pop_back();
        }
        q.push(value);
        deq.push_back(value);    
    }
    
    int pop_front() {
    
        if(q.empty()){
    
            return -1;
        }

        if(deq.front() == q.front()){
    
            deq.pop_front();
        }
        int ans = q.front();
        q.pop();
        return ans;
    }
};

如何解决 O(1) 複雜度的 API 設計題