LeetCode155—Min Stack

不念不忘少年蓝@ 2022-07-15 12:26 136阅读 0赞

## 原题 ##

[原题链接][Link 1]

> 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.

--------------------

## 分析 ##

正常push和pop都跟栈没有区别，但是多了一个可以从当前栈中取得最小值的方法。

除了普通的栈以外，需要一个额外的栈来记录最小值。

元素x进栈时，如果x比当前的最小值还要小，那么这个值是需要被记录的。  
元素x出栈时，如果x就是当前的最小值，那么这个曾经的最小值也是要出栈的。

### **代码** ###

class MinStack {
        private:
            stack <int> s1;//s1正常的栈
            stack <int> s2;//s2栈顶元素记录当前最小值
        public:
            MinStack() {
            }
    
    
    
        void push(int x) 
        {
            s1.push(x);
            if(s2.empty())
            {
                s2.push(x);
            }
            else
            {
                if(x<=s2.top())
                {
                    s2.push(x);
                }
            }
    
        }
    
        void pop() {
            int x=s1.top();
            s1.pop();
            if(x==s2.top())
                s2.pop();
        }
        int top() {
            return s1.top();
        }
        int getMin() {
            return s2.top();
        }
    };

[Link 1]: https://leetcode.com/problems/min-stack/