题目描述：

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. 解法一： 用一个栈s和一个指示当前栈中最小值min_elem的int，在push操作或者pop操作中更新min_elem。

class MinStack {public:    /** initialize your data structure here. */    int min_elem;    stack
     
       s;        MinStack() {        min_elem = INT_MIN;    }        void push(int x) {        if (min_elem == INT_MIN) {            min_elem = x;        }        else if (x < min_elem)        {            min_elem = x;        }        s.push(x);            }        void pop() {        if (s.empty()) {            return;        }        else        {            s.pop();            min_elem = INT_MIN;            stack
      
        temp_s;            while (!s.empty()) {                temp_s.push(s.top());                if (min_elem == INT_MIN) {                    min_elem = s.top();                }                else if (s.top() < min_elem) {                    min_elem = s.top();                }                s.pop();            }                        while (!temp_s.empty()) {                s.push(temp_s.top());                temp_s.pop();            }        }            }        int top() {                return s.top();            }        int getMin() {                return min_elem;            }};
      
     

 

这个解法不是很好的解法，虽然能够AC，但是效率在leetcode网站上的排名很低……

 

解法二：

使用两个栈，s和min。min记录当前栈中的一个递减序列，因为最小值的出栈操作仅和这个递减序列有关。

class MinStack {public:    /** initialize your data structure here. */    stack
     
       s;    stack
      
        min;        MinStack() {            }        void push(int x) {        if (s.empty() || x <= getMin()) {            min.push(x);        }        s.push(x);            }        void pop() {        if (s.top() == min.top()) {            min.pop();        }        s.pop();    }        int top() {        return s.top();            }        int getMin() {        return min.top();            }};
      
     

这个版本是leetcode官方的版本，但是效率也不是最好的，但是真的非常简洁，再次印证了简洁即高效的代码准则。