Min Stack

Question

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.

Tags

• stack
• data structure design

Thought

Traditional design of stack will perform badly in getMin function here, so it is necessary to design a new data structure for stack.

The straightforward idea is to store the minimum value in the stack directly such that getMin function doesn't need to traversal through the whole array.

The final structure of stack is below:

[(value, minStack), ...]

In the stack, each item is a tuple formed by two elements. The first one is the value at the corresponding position in the stack. The second one is the minimum value in the subsequence from the initial element to the corresponding position.

Code

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        item in the stack: (value, minValue)
        """
        self.stack = []

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


    def pop(self):
        """
        :rtype: void
        """
        if self.stack != []:
            self.stack.pop()

    def top(self):
        """
        :rtype: int
        """
        if self.stack == []:
            return None
        else:
            return self.stack[-1][0]


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



# 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()