Problem description:

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:

1
2
3
4
5
6
7
8
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.

Solution:

This problem is a little different from original stack, because it combines features of minheap and stack.

We can maintain two stacks. One is to store every element push into the MinStack, the other only stores the minimum element.

In the push function, whenever we need to push an element, check if it’s smaller than the top element in minstk.

In pop function, since every element are definitely in the total. We can check if the going-to-be-pop-out element from total is the same as the top element in minstk.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stk = []
        self.min = float('inf')
        self.prev_min = []

    def push(self, val: int) -> None:
        if val <= self.min:
            self.prev_min.append(self.min)
            self.min = val
        self.stk.append(val)

    def pop(self) -> None:
        if not self.stk:
            return None
        if self.top() == self.min:
            self.min = self.prev_min[-1]
            self.prev_min.pop()
        self.stk.pop()

    def top(self) -> int:
        return self.stk[-1]

    def getMin(self) -> int:
        if not self.stk:
            return None
        return self.min
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> total;
    stack<int> minstk;
    
    void push(int x) {
        total.push(x);
        if(minstk.empty() || x<= minstk.top())
            minstk.push(x);
    }
    
    void pop() {
        if(total.top() == minstk.top()) minstk.pop();
        total.pop();
    }
    
    int top() {
        return total.top();
    }
    
    int getMin() {
        return minstk.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

time complexity: $O(1)$
space complexity: $O(n)$
reference: