leetcode Question: Min Stack

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.

Analysis:

There are several ways to solve this problem.
(1) Use an extra stack to store the minimum value. The space is O(n), time O(1)
(2) Use a variable to store the minimum value. The time is O(n), space O(1)

Note that, in the python code, a little modification is needed to pass the OJ test.
Just using two stacks is not satisfied with the memory requirement.
So, the min stack stores [min_val, count] instead of each min_val.
e.g.,
Push into Stack:
st     min_st
2      [2,1]

st     min_st
0      [0,1]
2      [2,1]

st     min_st
3    
0      [0,1]
2      [2,1]

st     min_st
0
3    
0      [0,2]
2      [2,1]

Pop:
st     min_st
3    
0      [0,1]
2      [2,1]

st     min_st
0      [0,1]
2      [2,1]

st     min_st
2      [2,1]




Code(C++):


class MinStack {
    deque<int> st;
    int minVal;
public:
    void push(int x) {
        if (st.empty() || x<minVal){
            minVal = x;
        }
        st.push_front(x);
    }

    void pop() {
        if (st.front() == minVal){
            st.pop_front();
            minVal=INT_MAX;
            for (deque<int>::iterator it = st.begin();it!=st.end();it++){
                minVal = min(minVal,*it);
            }
        }else{
            st.pop_front();
        }
        
    }

    int top() {
        return st.front();
    }

    int getMin() {
        return minVal;
    }
};


Code(Python):

class MinStack:
    # @param x, an integer
    # @return an integer
    def __init__(self):
        self.l_num = []
        self.minval = []
    
    def push(self, x):
        if len(self.l_num) == 0 or len(self.minval) == 0:
            self.minval.append([x,1])
        else:
            if x < self.getMin():
                self.minval.append([x,1])
            elif x == self.getMin():
                self.minval[-1][1] += 1
        self.l_num.append(x)
            
    # @return nothing
    def pop(self):
        if self.l_num[-1] == self.minval[-1][0]:
            self.l_num.pop(-1)
            if (self.minval[-1][1]>1):
                self.minval[-1][1] -= 1
            else:
                self.minval.pop(-1)
        else:
            self.l_num.pop(-1)
            
        
    # @return an integer
    def top(self):
        return self.l_num[-1]

    # @return an integer
    def getMin(self):
        return self.minval[-1][0]
        


2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Your pop() is taking O(n) time complexity it can be done in O(1).
    Just use an extra stack to handle the minimum value at the moment.

    ReplyDelete