Min Stack

155. Min Stack

Solution

1. When an element is pushed, it doesn’t have to update the min value.

2. Only when the new min is pushed/popped, min get updated.

3. We can bind min with the value, such that when an element is pushed/popped, we can know if it affects the min.

4. Store the information in a list of tuple (x, min). Thus the last element always contains the min.

def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    if not self.stack:
        self.stack.append((x, x))
    else:
        self.stack.append((x, min(self.stack[-1][1], x)))