Poison

剑指 Offer 59 - II. 队列的最大值

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
public class MaxQueue {

private final Queue<Integer> queue;
private final Deque<Integer> deque; // 非严格递减队列

public MaxQueue() {
this.queue = new LinkedList<>();
this.deque = new LinkedList<>();
}

public int max_value() {
if (deque.isEmpty()) {
return -1;
} else {
return deque.peekFirst();
}
}

public void push_back(int value) {
queue.offer(value);

while (!deque.isEmpty() && value >= deque.peekLast()) {
deque.pollLast();
}
deque.offerLast(value);
}

public int pop_front() {
if (queue.isEmpty()) {
return -1;
} else {
int value = queue.poll();
if (value == deque.peekFirst()) {
deque.pollFirst();
}
return value;
}
}

}
Reference

剑指 Offer 59 - II. 队列的最大值