C++ compact solution


  • 2
    C

    General idea is to create an extra stack 'mins' to keep track of the min value sofar. Avoid unnecessary min value by inserting to 'mins' only if the new value is less than or equal to the current top value in 'mins'.

    class MinStack {
    public:
        void push(int x) {
            s.push(x);
            if (mins.empty() || x<=mins.top()) {
                mins.push(x);
            }
        }
    
        void pop() {
            int temp = s.top();
            s.pop();
            if (temp == mins.top()) {
                mins.pop();
            }
        }
    
        int top() {
            return s.top();
        }
    
        int getMin() {
            return mins.top();
        }
    
    private:
        stack<int> s;
        stack<int> mins;
    };
    

    http://changhaz.wordpress.com/2014/11/09/leetcode-min-stack/


  • 0
    T

    I also submitted this solution, but got a memory exceeded limit error...


  • 0
    C

    Exactly the same code? If not please copy paste your code here.


  • 0
    T

    you might have someting wrong in you code ........check it


  • 0
    T

    maybe somebody can help me out here.

    class MinStack {
    vector<int> regvec;
    vector<int> minvec;
    public:
    void push(int x) {
    if(minvec.empty()||x<=minvec.back())
    {
    minvec.push_back(x);
    }
    regvec.push_back(x);
    }

    void pop() {
        if(regvec.empty()) return;
        
        int x=regvec.back();
        
        regvec.pop_back();
        if(!minvec.empty()&&x==minvec.back())
        {
            minvec.pop_back();
        }
    }
    
    int top() {
        return regvec.back();
    }
    
    int getMin() {
        return minvec.back();
    }
    

    };


  • 0
    T
    This post is deleted!

  • 0
    C

    I experienced the same problem. interestingly, I used python to rewrite the code in the same way, it was accepted.


  • 0
    W

    Simpler and shorter solution but got MLE. Guess there are some bugs in LC's test programs.

    class MinStack {
    vector<int> s_, m_;
    public:
    void push(int x) {
        if(m_.empty() || x < s_[m_.back()])
            m_.push_back(s_.size());
        s_.push_back(x);
    }
    
    void pop() {
        if(s_.empty())
            return;
        const int v = s_.back();
        s_.pop_back();
        if(!m_.empty() && s_.size() == m_.back())
            m_.pop_back();
    }
    
    int top() {
        return (s_.empty() ? 0 : s_.back());
    }
    
    int getMin() {
        return (m_.empty() ? 0 : s_[m_.back()]);
    }
    };
    

    The idea is storing index instead of value in the min stack, then I don't need to store all the elems of the same value, e.g. "1 1 1 1 1 1". I only store index 0 in min stack, but not all the elems.


  • 0
    Y

    You use the vector to simulate the stack. That's the root cause. I had the same error as yours. The solution is accepted only after replacing the vector with stack.


  • 0
    H

    ... I use the same way, but get Memory Limit Exceeded


  • 0
    S

    i do not think your solution will work for the case: push(3), push(1), push(2), pop(), pop(), getMin(). For this case, your solution will return 2, but it should be 3


  • 0
    C

    I tried with map then vector and got MLE both, maybe vector reserved too many memory.


  • 0
    Y

    Compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way.

    Here is a good explanation:
    http://www.cplusplus.com/reference/vector/vector/


  • 0
    Y

    pay attention to this line:
    void push(int x) {
    if(m_.empty() || x < s_[m_.back()])

    maybe you need replace '<' by '<=' !
    assuming that 1 is minimum, you push 1,1,1,
    when you have to pop 1, there is only one '1' in vector but you have to pop three times


  • 0
    W

    Well, that's why I store s_.size() in m_ instead of x. You can see also in 'void pop()' that I pop up the element iff (!m_.empty() && s_.size() == m_.back()). So if there are many 1s, I only store the first 1's index in m_.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.