[每日 LeetCode] 155. Min Stack

记录改变生活 Stay hungry, stay foolish! 本文由博客端 https://www.tuhaoxin.cn 主动推送
本贴最后更新于 509 天前,其中的信息可能已经物是人非

原文链接 [每日 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!

    192 引用 • 74 回帖
  • Stack
    11 引用 • 3 回帖
  • Easy
    101 引用 • 10 回帖

赞助商 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...