剑指offer 68-2. 二叉树的最近公共祖先

题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制：

1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

题解

(队列) O(n)

使用两个队列，一个普通队列 q 用来存储元素，一个双端队列用来维护队列 q 中的最大值。

push_back(value): 如果 max_q 的最大值小于当前值 val，则一直弹出队尾，然后将当前值压入队列 q 和 max_q 中。
pop_front(): 弹出队列 q 的队头并返回，同时如果队头正好是 max_q 的队头，则 max_q 也要弹出队头。
max_value(): 返回 max_q 的队头即可，队头就是最大值。

时间复杂度

O(n)

空间复杂度

O(n)

C++ 代码

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

    MaxQueue() {

    }
    
    int max_value() {
        if (max_q.empty()) return -1;
        return max_q.front();
    }
    
    void push_back(int value) {
        while (max_q.size() && max_q.back() < value) max_q.pop_back();
        q.push(value);
        max_q.push_back(value);
    }
    
    int pop_front() {
        if (q.empty()) return -1;
        int t = q.front();
        q.pop();
        if (t == max_q.front()) max_q.pop_front();
        return t;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

Java 代码

class MaxQueue {
    Queue<Integer> q;
    LinkedList<Integer> max_q;

    public MaxQueue() {
        q = new LinkedList<>();
        max_q = new LinkedList<>();
    }
    
    public int max_value() {
        if (max_q.isEmpty()) return -1;
        return max_q.getFirst();
    }
    
    public void push_back(int value) {
        while (!max_q.isEmpty() && max_q.getLast() < value) {
            max_q.removeLast();
        }
        q.add(value);
        max_q.add(value);
    }
    
    public int pop_front() {
        if (q.isEmpty()) return -1;
        int t = q.poll();
        if (t == max_q.getFirst()) {
            max_q.removeFirst();
        }
        return t;
    }
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

Python 代码

class MaxQueue:

    def __init__(self):
        self.q = deque()
        self.max_q = deque()

    def max_value(self) -> int:
        if not self.max_q:
            return -1
        return self.max_q[0]

    def push_back(self, value: int) -> None:
        while self.max_q and self.max_q[-1] < value:
            self.max_q.pop()
        self.q.append(value)
        self.max_q.append(value)

    def pop_front(self) -> int:
        if not self.q:
            return -1
        t = self.q.popleft()
        if t == self.max_q[0]:
            self.max_q.popleft()
        return t

# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

上一篇：剑指offer 68-1. 二叉搜索树的最近公共祖先