I only store:
- The current
minamong the stack elements.
- For each pushed element, the difference to the previous
min. If the pushed element changes
min, because it is even smaller, then this difference is negative. If it's larger than the previous
min, then the difference is positive.
pop, I need to pop the last difference and undo its change to
min (if any). For
top, I need to add the current min and the last difference (if it's positive, i.e., if the last element was larger than the minimum).
class MinStack: def __init__(self): self.min = 2 ** 32 self.diffs =  def push(self, x): self.diffs += x - self.min, self.min = min(self.min, x) def pop(self): diff = self.diffs.pop() self.min -= min(diff, 0) def top(self): return self.min + max(self.diffs[-1], 0) def getMin(self): return self.min