面试题59 - II. 队列的最大值

题目：

面试题59 - II. 队列的最大值



注：API参考：
队列Queue、双端队列Deque

1. Deque API：



2. Queue API：

//将指定元素插入双向队列开头
void addFirst (Object e );

// 将指定元素插入双向队列末尾
void addLast (Object e );

// 返回对应的迭代器，以逆向顺序来迭代队列中的元素
Iterator descendingIterator ();

// 获取但不删除双向队列的第一个元素
Object getFirst ();

// 获取但不删除双向队列的最后一个元素 
Object getLast ();

// 将指定元素插入双向队列开头 
boolean offerFirst (Object e );

// 将指定元素插入双向队列结尾 
boolean offerLast (Object e );

// 获取但不删除双向队列的第一个元素，如果双端队列为空则返回 null 
Object peekFirst ();

// 获取但不删除双向队列的最后一个元素，如果此双端队列为空则返回 null 
Object peekLast ();

// 获取并删除双向队列的第一个元素，如果此双端队列为空则返回 null
Object pollFirst ();

// 获取并删除双向队列的最后一个元素，如果此双端队列为空则返 null 
Object pollLast ();

// 退栈出该双向队列中的第一个元素 
Object pop ();

// 将元素入栈进双向队列栈中
void push (Object e );

// 获取并删除该双向队列的第一个元素 
Object removeFirst ();

// 删除双向队列第一次出现的元素 e 
Object removeFirstOccurrence (Object e );

// 获取并删除双向队列的最后一个元素 
removeLast();

// 删除双向队列最后一次出现的元素 e 
removeLastOccurrence(Object e);

题解：

1. 题解一：暴力

思路：

直接实现一个普通的队列，查询最大值时遍历计算。

2. 题解二：维护一个单调的双端队列

2.


3.

4.

5.

代码：

1. 代码一：暴力

/**
 * code面试题59_2
 */
import java.util.*;

public class code面试题59_2 {

    // 解法一：
    public static class MaxQueue {

        int queue[] = new int[20000]; // java生成数组的默认值为 0
        int begin = 0, end = 0;

        public MaxQueue() {

        }

        public int max_value() {
            if (begin == end) {
                return -1;
            }
            int ans = -1;
            for (int i = begin; i <= end; i++) {
                if (queue[i] > ans) {
                    ans = queue[i];
                }
            }
            return ans;
        }

        public void push_back(int value) {
            queue[end++] = value;
        }

        public int pop_front() {
            if (begin == end) {
                return -1;
            }
            return queue[begin++];
        }
    }

    public static void main(String[] args) {
        MaxQueue obj = new MaxQueue();
        obj.push_back(1);
        obj.push_back(2);
        int param_1 = obj.max_value();
        int param_2 = obj.pop_front();
        System.out.println(param_1 + " " + param_2);
    }
}

2. 代码二：维护一个单调的双端队列

/**
 * code面试题59_2
 */
import java.util.*;

public class code面试题59_2 {

    // 解法二：
    public static class MaxQueue {

        Queue<Integer> queue;
        Deque<Integer> deque;

        public MaxQueue() {
            queue = new LinkedList<>(); // 队列：插入和删除
            deque = new ArrayDeque<>(); // 双端队列：获取最大值
        }

        public int max_value() {
            if (deque.isEmpty()) {
                return -1;
            }
            return deque.peekFirst(); // 双端队列的队首为que的最大值
        }

        public void push_back(int value) {
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.pollLast(); // 将deq队尾小于value的元素删掉
            }
            deque.offerLast(value);// 将value放在deq队尾
            queue.offer(value); // value入队
        }

        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            int result = queue.peek(); // 获得队首元素
            if (deque.peekFirst() == result) {
                deque.pollFirst(); // 如果出队的元素是当前最大值，将deq的队首出队
            }
            queue.poll();
            return result;
        }
    }

    public static void main(String[] args) {
        MaxQueue obj = new MaxQueue();
        obj.push_back(1);
        obj.push_back(2);
        int param_1 = obj.max_value();
        int param_2 = obj.pop_front();
        System.out.println(param_1 + " " + param_2);
    }
}

参考：

1. 【LeetCode】面试题59 - II. 队列的最大值
2. 面试题59 - II. 队列的最大值
3. 如何解决 O(1) 复杂度的 API 设计题
4. 官方方法2“双端队列”动画图解
5. Java队列与双端队列
6. Java 双端队列 Deque 的 ArrayDeque
7. 队列Queue、双端队列Deque