Hi,
I’m trying to solve the problem 9.12 and I found almost by myself the trick. Now, I was wondering if it would be even better to apply the same solution as 9.1, basically storing in the deque the number of apparitions together with the possible max element. Large elements tend to accumulate in the head of the deque.
I was hinting at using a queue and a deques, as in 1st solution, instead of 2 stacks.
Hey Bogdan,
I didn’t quite understand your question and could you elaborate it more?
Sorry, before I posted this I haven’t read the second solution of this problem I can confirm that there are 2 solutions in the book, second being similar to what I talked about above.
Hi there,
for the second solution and the implementation of max(), which is on page 149 in the book of Java version.
if we have enqueue(2),enqueue(3),dequeue(),enqueue(1) and then max(). In this case, we get 1, not 2. Is that a mistake? since now 3 is in dequeue. Shall we compare both enqueue.max() and dequeue.max() and return the larger one?
Thanks!
Hey Xiaoran,
Many thanks for your report. In fact, the return part when enqueue is not empty is not correct. Following is the refined code:
public Integer max() {
if (!enqueue.empty()) {
return dequeue.empty() ? enqueue.max()
: Math.max(enqueue.max(), dequeue.max());
}
if (!dequeue.empty()) {
return dequeue.max();
}
throw new NoSuchElementException("Cannot get max() on empty queue.");
}