An undo history stores the cost of each edit. Besides the usual stack operations, the editor wants to know the cheapest edit still in the history at any moment.
Write a class TrackedStack:
TrackedStack()creates an empty stack.push(x)putsxon top.pop()removes the top value and returns it.top()returns the top value without removing it.get_min()returns the smallest value currently in the stack.
pop, top and get_min are only called when the stack is non-empty. Values may repeat.
s = TrackedStack()
s.push(5)
s.push(2)
s.push(7)
s.get_min() # 2
s.pop() # 7
s.push(2)
s.pop() # 2
s.get_min() # 2 (the first 2 is still there)
s.pop() # 2
s.get_min() # 5
s.top() # 5
Constraints: up to 3 * 10^5 calls; values are in [-10^9, 10^9].
Calling min() on the whole stack is O(n) per query and too slow. Every method must run in O(1).
Show hint
the minimum only changes when you push or pop. What if, alongside each value, you remember what the minimum was at the moment it was pushed?