Max from the list after adding a new item and deleting the oldest

Question

I have a list of integers with the maximum element, and I need to track the maximum element in the list:

[3, 1, 2] (3 is the max) 

Each time period, I get a new random element, add it to the end of the list and delete the first element of the list in constant time. So, at the end of the current period, my list will look like this:

  [3, 1, 2] (3 is the max) -> [3, 1, 2, -5] (don't care about max at this moment) -> [1, 2, -5] (now 2 is the max) 

I could keep the priority queue specified in the values ​​in the list by typing and deleting O (log (n)), but I was interested to know if there is a more efficient (possibly [amortized] constant time?).

Answer 1

There are algorithms with O (1) amortized complexity:

with deque: Can the min / max of a moving window reach in O (N)?

with two stacks: Implement a queue in which push_rear (), pop_front () and get_min () are all constant-time operations

Answer 2

Cases:

• New> = CurrentMax and First anything: CurrentMax has been updated to New;
• New <CurrentMax and First <Max. Current: no change;
• New <CurrentMax and First> = Current Max: search to determine the new CurrentMax;

But:

To make the 3rd random executor, you need to maintain a (doubly connected) list of items in nesting order and a tree in numerical order. Then you just do insert / delete both in the list and in the tree and read the new max current from the tree. This is as effective as implementing a tree, O (N) to create a list of placement orders, and O (N log N) to build a ranking tree.

The data structure for storing list items will look something like this:

 public class Element { Element PrevInsertionOrder; Element NextInsertionOrder; Element RankingTreeParent; Element RankingTreeLeftChild; Element RankingTreeRightChild; int Data; } 

Update:

By storing the second (doubly linked) list of different key values ​​with the number of matches (instead of the second tree above), it is possible that O (1) time for the MAX definition to be performed is possible.