LeetCode [stack] 155.Min Stack (implemented in C + + and Python)

155 Min Stack

[title]

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:

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.

[problem solving C + +]

'in constant time' requires a constant time, that is, a minimum value cannot be found by traversal. At the beginning, I thought of setting up two variables, a record minimum and a record second minimum. But there are many bugs in my code. When the number of two consecutive pop s is the minimum value, the two variables will disappear. After reading the comments below, some people use two stacks, but the title requires Design a stack. So I found another way to find a blog and found a very ingenious way~

Set a variable minNum to record the minimum value. When the element is no more than minNum, the minNum will be added to the stack and then the element will be added to the stack. This really saves the second smallest variable! When out of stack, when the out of stack element happens to be the minimum value, the top of stack element is the second minimum value after out of stack. Update minNum at this time!

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st;
    int minNum;
    MinStack() {
        //Initialize to a large value
        minNum = 0x7fffffff;
    }
    
    void push(int x) {
        //When the stack element ≤ minimum
        //Be sure to add =, because there can be several minimum values at the same time, which should be saved
        if(x<=minNum)
        {
            //Second smallest value in stack
            st.push(minNum);
            //Update minimum
            minNum = x;      
        }
        //Push
        st.push(x);
    }
    
    void pop() {
        int topNum = st.top();
        //If the outbound element is exactly the minimum
        if(topNum==minNum)
        {
            //First out stack
            st.pop();
            //At this time, the stack top element is the second smallest value before, which is the current minimum value
            minNum = st.top();
        }
        //This can be a normal stack exit without entering the if statement
        //It can also be that after entering the if statement, the second small value copy element will be pushed out
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minNum;
    }
};

/**
 * 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();
 */

[problem solving Python]

Python is lazy. The function min()

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

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

    def getMin(self) -> int:
        return min(self.stack)


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

Tags: Python

Posted on Fri, 08 Nov 2019 10:29:27 -0800 by ElectricMessiah