In java, I'm implementing a deque using LinkedList. Deque<Integer> deque = new LinkedList<>().
My deque has the following methods:
addFirst(Integer x)
addLast(Integer x)
Integer removeFirst()
Integer removeLast() and
Integer max()
The max() method needs to find the max element in the deque in O(1) amortized time and return it.
Currently I am using Deque<Integer> max_deque = new LinkedList<>() to store the max element of the deque but I am having trouble updating the max element in this data structure when the add and remove operations are performed on deque.
How do I go about implementing this so that the max element gets updated and returned in O(1) amortized time? Thank you!