劍指–隊列的最大值

1，題目：

2，思路：

看下面的代碼

3，代碼：

寫法一：（隊列+兩個棧）：

class MaxQueue {

/*
    等下，我們使用一個隊列正常的存放資料，
    然後使用維護一個單調棧，棧頂為最大值
    再加一個輔助棧

    元素插入順序：1   3   5   5   2   6   1   2

    （棧的元素最左邊為棧底，最右邊為棧頂，隊列也一樣）
    插入 1：
    queue = {1}
    stack = {1}
    插入 3
    queue = {3, 1}
    stack = {3}
    (
        這裡為什麼 stack 是 3？之前的 1 哪去了？
        因為 1 比 3 先插入，是以最先 poll() 的必定會是 1，而在 poll 3 之前，無論 1 是否存在，最大值都會是 3，是以 1 的存在無關緊要
        這裡我們就可以知道，隻要後面進來一個比之前存儲元素都要大的，那麼前面的小元素都無關緊要了，清空棧，隻入棧這個最大元素
    )
    插入 5
    queue = {5, 3, 1}
    stack = {5}
    插入 5
    queue = {5，5, 3, 1}
    stack = {5，5}
    (
        插入跟棧頂元素一樣大的值，這個就不必多說什麼了吧，直接入棧即可
    )
    插入 2
    queue = {2, 5, 5, 3, 1}
    stack = {2, 5, 5}
    (
        這裡為什麼 2 又存在了？ 而且是在棧底？
        因為 5 比 2 先插入，是以最先 poll() 的一定會是 5，那麼當 poll 5 的時候，前面的 1 和 3 也都已經 poll() 了
        那麼隊列剩下的就是 5 後面插入元素的最大值，即 2，是以我們需要留下 2
    )
    插入 6
    queue = {6, 2, 5, 5, 3, 1}
    stack = {6}
    插入 1
    queue = {1, 6, 2, 5, 5, 3, 1}
    stack = {1, 6}
    插入 2
    queue = {2, 1, 6, 2, 5, 5, 3, 1}
    stack = {2, 6}
    (
        這裡為什麼是 2 在底部？ 1 哪去了？
        6 比 後面的 1 和 2 都先插入，是以在 poll 6 之前， 6 是最大的
        而 1 比 2 先插入，是以在 poll 2 之前，前面的 1 是否存在無關緊要，當 poll 6 後，最大值就會是 6 後面插入元素的最大值。即 2
        這裡我們就知道，我們當插入元素比 棧頂元素 小的時候，我們需要清空掉 棧内所有比 插入元素小的值，然後入棧
        （這裡做法就是 面試題 03.05. 棧排序 的做法）
    )
    */




    Queue<Integer> queue;//隊列
    Deque<Integer> stack;//棧
    Deque<Integer> helper_stack;//輔助棧
    public MaxQueue() {
        queue = new LinkedList<>();
        stack = new LinkedList<>();
        helper_stack = new LinkedList<>();
    }
    
    public int max_value() {
        if(queue.isEmpty()){
            return -1;
        }
        return stack.peek();//傳回最大值
    }
    
    public void push_back(int value) {
        queue.add(value);
        //棧為空，直接入棧
        if(stack.isEmpty()){
            stack.push(value);
        }else{
            if(stack.peek() < value){   //當棧頂元素比目前元素小，那麼清空棧，然後将 value 入棧
                stack.clear();
                stack.push(value);
            }else if(stack.peek() == value){    //當棧頂元素等于目前元素，那麼直接入棧
                stack.push(value);
            }else{
                while(!stack.isEmpty() && stack.peek() >= value){   //當棧頂元素大于目前元素，将大于等于 value 的值壓入輔助棧
                    helper_stack.push(stack.pop());
                }
                //壓入插入元素
                helper_stack.push(value);
                //清空 stack 
                stack.clear();
                //重新将輔助棧的值壓回 stack
                while(!helper_stack.isEmpty()){
                    stack.push(helper_stack.pop());
                }
            }
        }
    }
    
    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        int temp = queue.poll();
        if(stack.peek() == temp){
            stack.pop();
        }
        return temp;
    }
}

           

寫法二：（隊列+雙端隊列）：

class MaxQueue {
    Queue<Integer> que;
    Deque<Integer> deq;

    public MaxQueue() {
        que = new LinkedList<>();  //隊列：插入和删除
        deq = new LinkedList<>();  //雙端隊列：擷取最大值
    }
    
    public int max_value() {
        return deq.size()>0?deq.peek():-1;  //雙端隊列的隊首為que的最大值
    }
    
    public void push_back(int value) {
        que.offer(value);  //value入隊
        while(deq.size()>0 && deq.peekLast()<value){
            deq.pollLast();  //将deq隊尾小于value的元素删掉
        }
        deq.offerLast(value);  //将value放在deq隊尾
    }
    
    public int pop_front() {
        int tmp = que.size()>0?que.poll():-1;  //獲得隊首元素
        if(deq.size()>0 && deq.peek().equals(tmp)){
            deq.poll();  //如果出隊的元素是目前最大值，将deq的隊首出隊
        }
        return tmp;
    }
}


           

寫法三：隊列+雙端連結清單：

public class MaxQueue {

    Queue<Integer> queue;
    LinkedList<Integer> max;
    public MaxQueue() {
        queue = new LinkedList<>();
        max = new LinkedList<>();//LinkedList是雙端連結清單
    }
    
    public int max_value() {
        return max.size()==0?-1:max.getFirst();
    }
    
    public void push_back(int value) {
        queue.add(value);
        while(max.size()!=0&&max.getLast()<value){//注意：這裡第二個判斷條件不能帶等号，即max中對于目前queue中的具有相同值的元素會全部存儲，而不是存儲最近的那個。
            max.removeLast();
        }
        max.add(value);
    }
    
    public int pop_front() {
        if(max.size()!=0&&queue.peek().equals(max.getFirst()))//Integer類型的值的比較不能直接使用==
            max.removeFirst();
        return queue.size()==0?-1:queue.poll();
    }

}