letecode [155] - Min Stack

小鱼儿 2021-11-04 11:04 156阅读 0赞

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.

**题目大意**：

设计一个最小栈类，基于STL模板栈基础上实现，主要是实现在线性时间内获得栈中的最小值。

**理  解：**

利用两个栈，一个栈item保存所有元素，另一个栈min保存最小值。

push时，若栈为空，则当前元素为最小值，压入栈item和栈min；栈非空时，判断比较元素与min栈顶元素，将较小者压入min栈.

pop时，两个栈栈顶元素均出栈.

getMin时，返回min栈顶元素.

top时，返回item栈顶元素。

**代 码 C++：**

class MinStack {
    private:
        stack<int> item;
        stack<int> min;
    public:
        /** initialize your data structure here. */
        MinStack() {
            
        }
        
        void push(int x) {
            item.push(x);
            if(min.empty()){
                min.push(x);
            }else{
                if(x<=min.top())
                    min.push(x);
                else
                    min.push(min.top());
            }
        }
        
        void pop() {
          
            min.pop();
            item.pop();
        }
        
        int top() {
            return item.top();
        }
        
        int getMin() {
            return min.top();
        }
    };
    
    /**
     * 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();
     */

**运行结果：**

执行用时 : 68 ms, 在Min Stack的C++提交中击败了45.46% 的用户

内存消耗 :  16.9 MB, 在Min Stack的C++提交中击败了51.62% 的用户

转载于:https://www.cnblogs.com/lpomeloz/p/10999853.html