Share my clean AC C++ solution, with explanation.


  • 14
    K

    The key idea is use a another stack to store the minimum value of the corresponding stack. Put differently, min[i] equals the minimum element where data[i] is the top of this sub-stack.

    We can use a full size of min where its size equals the data's, but it's not necessary.

    Idea

    • We should pop the element in min IFF there's match of data.top().

    • If we have multiple same minima, for example [0, 1, 0] in data, then the min should be [0, 0].
      Otherwise, the the pop operation wouldn't work properly, since that you need 2 0s.
      As a result, we should push the element if x <= min.top().

    Code

    class MinStack {
        
        stack<int> data;
        stack<int> min;
    
    public:
    
        void push(int x) {
            
            // If empty
            if (min.empty()) {
                data.push(x);
                min.push(x);
            }
            
            // Not empty
            else {
                data.push(x);
                if (x <= min.top())
                    min.push(x);
            }
    
        }
    
        void pop() {
            
            if (!min.empty()) {
                if (data.top() == min.top())
                    min.pop();
                data.pop();
            }
        }
    
        int top() {
            return data.top();
        }
    
        int getMin() {
            return min.top();
        }
    };

  • 0
    P

    Good explanation and method!! I always got a MLE...


  • -4
    Y

    Here is the situation that your code seems wrong, why it could pass the test?:

    Here are the arrays that should be pushed into the data stack: {7,8,4,3,5,6}

    Then your min stack will have the elements from bottom to top: {7,4,3}

    Then do four times pop(), and then do the getMin(), your answer should be 4. However, it is not in the stack data.


  • 0
    S

    Nothing's wrong with his/her solution. After doing pop() four times, data stack is {7,8} and min stack will be {7}. getMin() returns 7, which is right.


  • 1
    B

    push() could be simplified.

    void push(int x) {
        data.push(x);
        if(min.empty() || x <= min.top())
            min.push(x);
    }

  • -1
    J

    Instead of a stack of integers, use a stack of pairs where the first key is the value, the second is the min value on the stack:

    stack<pair<int, int>>

  • 0
    K

    Thank you for your comment. In my opinion, using 2 stacks will reduce the usage of space. For example, say a stack with N elements, and the minimum is the first element pushed onto the stack. Then your method will have to push N duplicates of the minimum, which is not necessary here. You don't need to store the minimum every time since it's not updated.


  • 0
    K

    Thank you for your comment. However after 4 times of pop, the stack should be [7, 8]. Because before the 4th pop, the current top of the stack and the min stack are both 4, which should all be poped.


  • 0
    A

    Can you please tell me when you titled "clean AC C++ solution", what does "AC" stands for?


  • 0
    K

    I think AC is the abbreviation of ACCEPTED. It weird at the beginning though.


  • 0
    R

    Thanks for code.

    In my opinion,....the question ask for implement a "STACK"...but not really use a "STL stack".
    It won't be accept in interview though...just saying.


Log in to reply
 

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