原文链接 [链接] Description: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. p ..

[每日 LeetCode] 155. Min Stack

本贴最后更新于 287 天前,其中的信息可能已经物是人非

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

Description:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

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

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    164 引用 • 61 回帖
  • Stack
    9 引用 • 3 回帖
  • Easy
    101 引用 • 10 回帖
回帖
请输入回帖内容...