栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

剑指 Offer 30. 包含min函数的栈

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指 Offer 30. 包含min函数的栈

剑指 Offer 30. 包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

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

提示:

各函数的调用总次数不超过 20000 次

解法一:辅助栈

public class MinStack {
    Stack minStack;
    Stack stack;
    public MinStack() {
        minStack = new Stack<>();
        stack = new Stack<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        stack.push(x);
        minStack.push(Math.min(minStack.peek(),x));


    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
       return minStack.peek();
    }
}

解法二:辅助链表 添加节点

public class MinStack {
    private Node head;
    public MinStack() {

    }

    public void push(int x) {
        if (head==null){
            head = new Node(x,x,null);
        }else{
            head = new Node(x,Math.min(head.min,x),head);
        }

    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        return  head.val;
    }

    public int min() {
        return head.min;
    }
}
class  Node {
    int val;
    int min;
    Node next;


    public Node(int val, int min, Node next) {
        this.val = val;
        this.min = min;
        this.next = next;
    }
}
  • 创建者:师晓峰
  • 创建时间:2022/6/1 18:54
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/944945.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号