A 32ms C++ Solution using two vectors


  • 4
    Y
    class MinStack {
    public:
        vector<int> stack; 
        vector<int> stmin = {INT_MAX};
        void push(int x) {
            if(x <= stmin[stmin.size() - 1]) stmin.push_back(x);
            stack.push_back(x);
        }
    
        void pop() {
            if(stack[stack.size() - 1] == stmin[stmin.size() - 1]) stmin.pop_back();
            stack.pop_back();
        }
    
        int top() {
            if(stack.size() == 0) return 0;
            return stack[stack.size() - 1];
        }
    
        int getMin() {
            return stmin[stmin.size() - 1];
        }
    };

  • 0
    Y

    For 'push(int x)', what if x is larger than the last element in stmin vector?


  • 0
    Y

    One of the objects of Min Stack problem is to retrieving the minimum element in the stack, so I record the smallest element found. If x is larger than the last element in stmin vector, this x has nothing to do with with minimum value, just push into regular stack but not in minimum value stack.


  • 0
    L

    When the first number pushed into the stack is a negative number, for example, -3, then getMin, the result is INT_MIN. The expected result is -3.
    If you want to make INT_MIN to be the first number of stmin, add "|| stmin.size() == 1" in the condition judgement, aka, if (x <= stmin[stmin.size() - 1] || stmin.size() - 1 == 0)

    if (x <= stmin[stmin.size() -1] || stmin.size() -1 == 0)

  • 0
    X

    You can't use vector as mentioned in the question that you can only use stack.


  • 0
    Y

    Hi, I checked the code in local, if I push a negative number number at very first and then getmin(), it will return the negative number I just push.


  • 0
    Y

    I don't think so. The problem is to design a stack and no comment of using other things. I'm glad if you can share me your code with me.


  • 0
    L

    啊,不好意思看错了。我以为你stmin的初始化值里是INT_MIN,现在才看清是INT_MAX,那是没错了。


  • 0
    Y

    呵呵,没事,我也经常犯这样的错误


Log in to reply
 

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