Leetcode C++《热题 Hot 100-9》155.最小栈

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Leetcode C++《热题 Hot 100-9》155.最小栈，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1916字，纯文字阅读大概需要3分钟。

内容图文

Leetcode C++《热题 Hot 100-9》155.最小栈

1. 题目
   设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

   push(x) – 将元素 x 推入栈中。
   pop() – 删除栈顶的元素。
   top() – 获取栈顶元素。
   getMin() – 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 思路

• 这个题目也比较简单，方案1:用两个栈，一个数据栈，一个辅助min栈（辅助min栈可以和数据栈同步更新，也可以min变化的时候再更新）剑指offer 21 包含min函数的栈-类似题目链接
• 更神奇的方案2：使用一个栈，外部记录min值，如果min值有变化，那将其加入到数据栈中，这个方法简直吓人太棒了
• 方案2-3参考：https://leetcode-cn.com/problems/min-stack/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
• 还有一些变种方案3：数据栈大小不变，外部维护一个min值，存储min值与原数据的差，差为负数表示min值有更新
• 时间复杂度三种方案都是O(n)，考虑空间复杂度，最节省空间的是方案3，所以来试下方案3

3. 代码

class MinStack {
public:
    /** initialize your data structure here. */
    //注意int在做减法操作时候，可能会超出int范围，所以需要使用long数据类型
    long min;
    stack<long> nums;

    MinStack() {
    }
    
    void push(int x) {
        if (nums.size() == 0) {
           min = x;
           nums.push(x-min);
           return;
        }
        else if (x < min) {
            nums.push(x-min);
            min = x;
        } else {
            nums.push(x-min);
        }
        
    }
    
    void pop() {
        if (nums.top() < 0)
            min = min - nums.top();
        nums.pop();
    }
    
    int top() {
        if (nums.top() < 0)
            return min;
        else {
            return min+nums.top();
        }
    }
    
    int getMin() {
        return min;
    }
};

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

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的Leetcode C++《热题 Hot 100-9》155.最小栈全部内容，希望文章能够帮你解决Leetcode C++《热题 Hot 100-9》155.最小栈所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端