跳转至

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

题目描述

请定义一个队列并实现函数 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

解法

方法一：双队列

我们维护两个队列 $q_1$ 和 $q_2$，其中 $q_1$ 用于存储所有元素，而 $q_2$ 用于存储当前队列中的最大值。

当获取队列中的最大值时，如果队列 $q_2$ 不为空，则队列中的最大值即为 $q_2$ 的队首元素；否则队列为空，返回 $-1$。

当向队列中添加元素时，我们需要将 $q_2$ 弹出所有队尾元素小于当前元素的元素，然后将当前元素添加到 $q_2$ 的队尾，最后将当前元素添加到 $q_1$ 的队尾。

当从队列中弹出元素时，如果 $q_1$ 为空，则返回 $-1$；否则，如果 $q_1$ 的队首元素等于 $q_2$ 的队首元素，则将 $q_2$ 的队首元素弹出，然后将 $q_1$ 的队首元素弹出；否则，只将 $q_1$ 的队首元素弹出。

以上操作的时间复杂度均为 $O(1)$，空间复杂度为 $O(n)$。其中 $n$ 为队列中的元素个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MaxQueue:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

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

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

    def pop_front(self) -> int:
        if not self.q1:
            return -1
        ans = self.q1.popleft()
        if self.q2[0] == ans:
            self.q2.popleft()
        return ans


# 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()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MaxQueue {
    private Deque<Integer> q1 = new ArrayDeque<>();
    private Deque<Integer> q2 = new ArrayDeque<>();

    public MaxQueue() {
    }

    public int max_value() {
        return q2.isEmpty() ? -1 : q2.peek();
    }

    public void push_back(int value) {
        while (!q2.isEmpty() && q2.peekLast() < value) {
            q2.pollLast();
        }
        q1.offer(value);
        q2.offer(value);
    }

    public int pop_front() {
        if (q1.isEmpty()) {
            return -1;
        }
        int ans = q1.poll();
        if (q2.peek() == ans) {
            q2.poll();
        }
        return ans;
    }
}

/**
 * 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();
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MaxQueue {
public:
    MaxQueue() {
    }

    int max_value() {
        return q2.empty() ? -1 : q2.front();
    }

    void push_back(int value) {
        while (!q2.empty() && q2.back() < value) {
            q2.pop_back();
        }
        q1.push(value);
        q2.push_back(value);
    }

    int pop_front() {
        if (q1.empty()) {
            return -1;
        }
        int ans = q1.front();
        q1.pop();
        if (q2.front() == ans) {
            q2.pop_front();
        }
        return ans;
    }

private:
    queue<int> q1;
    deque<int> q2;
};

/**
 * 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();
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
type MaxQueue struct {
    q1, q2 []int
}

func Constructor() MaxQueue {
    return MaxQueue{[]int{}, []int{}}
}

func (this *MaxQueue) Max_value() int {
    if len(this.q2) == 0 {
        return -1
    }
    return this.q2[0]
}

func (this *MaxQueue) Push_back(value int) {
    for len(this.q2) > 0 && this.q2[len(this.q2)-1] < value {
        this.q2 = this.q2[:len(this.q2)-1]
    }
    this.q1 = append(this.q1, value)
    this.q2 = append(this.q2, value)
}

func (this *MaxQueue) Pop_front() int {
    if len(this.q1) == 0 {
        return -1
    }
    ans := this.q1[0]
    this.q1 = this.q1[1:]
    if this.q2[0] == ans {
        this.q2 = this.q2[1:]
    }
    return ans
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Max_value();
 * obj.Push_back(value);
 * param_3 := obj.Pop_front();
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MaxQueue {
    private queue: number[];
    private deque: number[];

    constructor() {
        this.queue = [];
        this.deque = [];
    }

    max_value(): number {
        return this.deque[0] ?? -1;
    }

    push_back(value: number): void {
        this.queue.push(value);
        while (this.deque.length !== 0 && this.deque[this.deque.length - 1] < value) {
            this.deque.pop();
        }
        this.deque.push(value);
    }

    pop_front(): number {
        const res = this.queue.shift();
        if (res === this.deque[0]) {
            this.deque.shift();
        }
        return res ?? -1;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
use std::collections::VecDeque;
struct MaxQueue {
    queue: VecDeque<i32>,
    deque: VecDeque<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MaxQueue {
    fn new() -> Self {
        Self {
            queue: VecDeque::new(),
            deque: VecDeque::new(),
        }
    }

    fn max_value(&self) -> i32 {
        *self.deque.front().unwrap_or(&-1)
    }

    fn push_back(&mut self, value: i32) {
        self.queue.push_back(value);
        while !self.deque.is_empty() && *self.deque.back().unwrap() < value {
            self.deque.pop_back();
        }
        self.deque.push_back(value);
    }

    fn pop_front(&mut self) -> i32 {
        if self.queue.is_empty() {
            return -1;
        }
        let res = self.queue.pop_front().unwrap();
        if res == self.deque[0] {
            self.deque.pop_front();
        }
        res
    }
}/**
 * Your MaxQueue object will be instantiated and called as such:
 * let obj = MaxQueue::new();
 * let ret_1: i32 = obj.max_value();
 * obj.push_back(value);
 * let ret_3: i32 = obj.pop_front();
 */

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
var MaxQueue = function () {
    this.q1 = [];
    this.q2 = [];
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function () {
    return this.q2.length ? this.q2[0] : -1;
};

/**
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function (value) {
    while (this.q2.length && this.q2[this.q2.length - 1] < value) {
        this.q2.pop();
    }
    this.q1.push(value);
    this.q2.push(value);
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function () {
    if (!this.q1.length) {
        return -1;
    }
    const ans = this.q1.shift();
    if (this.q2[0] == ans) {
        this.q2.shift();
    }
    return ans;
};

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class MaxQueue {
    LinkedList<int> mvq;
    Queue<int> q;

    public MaxQueue() {
        mvq = new LinkedList<int>();
        q = new Queue<int>();
    }

    public int Max_value() {
        if (mvq.Count == 0) {
            return -1;
        }
        return mvq.First.Value;
    }

    public void Push_back(int value) {
        q.Enqueue(value);
        while (mvq.Count > 0 && mvq.Last.Value < value) {
            mvq.RemoveLast();
        }
        mvq.AddLast(value);
    }

    public int Pop_front() {
        if (q.Count == 0) {
            return -1;
        }
        int v = q.Dequeue();
        if (mvq.First.Value == v) {
            mvq.RemoveFirst();
        }
        return v;
    }
}

/**
 * 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();
 */

评论