155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.

• pop() -- Removes the element on top of the stack.

• top() -- Get the top element.

• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

The Idea: Have every element in the stack have an pointer index to the minimum element below it. When the stack is empty, the minimum element points to itself. Otherwise, we can incrementally build the stack so that we only need to compare the top element of the stack. Since the top of the stack is always going to minimum element, if the new element is smaller than the current minimum element, then it is going to update as the current minimum element of its substack. Otherwise have it point to the same minimum index as the previous stack element has.

Complexity: Constant time for all operations. O(n) space.

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.s = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if len(self.s) > 0:
            cur_min_i = self.s[-1][1]
            cur_min   = self.s[cur_min_i][0]
            if x < cur_min:
                self.s.append((x, len(self.s)))
            else:
                self.s.append((x, self.s[-1][1]))
        else:
            self.s.append((x, 0))

    def pop(self):
        """
        :rtype: void
        """
        self.s.pop()

    def top(self):
        """
        :rtype: int
        """
        return self.s[-1][0]

    def getMin(self):
        """
        :rtype: int
        """
        return self.s[self.s[-1][1]][0]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()