[每日 LeetCode] 155. Min Stack

原文链接 [每日 LeetCode] 155. Min Stack

Description:

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

本题要求设计一个最小栈，即在原有栈的方法中加入 getMin() 方法。

思路一：最开始想到的是使用 vector 来实现，最后运行起来效率太低，不推荐。

思路二：使用两个栈，一个正常操作，另一个栈保证栈顶元素最小，这个效率很高，也是 LeetCode 高赞答案，值得推荐。

C++ 代码（思路一，不推荐）

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    void push(int x) {
        vec.push_back(x);
    }
    void pop() {
        vec.pop_back();
    }
    int top() {
        return vec[vec.size() - 1];
    }    
    int getMin() {
        return *min_element(vec.begin(), vec.end());
    }   
private:
    vector<int> vec;
};
/**
 * 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();
 */
​

运行时间：208ms

运行内存：17.1M

C++ 代码（思路二，推荐）

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

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

运行时间：32ms

运行内存：17M