leetcode 155

题目描述：

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<int> 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<int> 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<int> s;
    stack<int> 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官方的版本，但是效率也不是最好的，但是真的非常简洁，再次印证了简洁即高效的代码准则。