【LeetCode】包含 min 函数的栈 Java 题解

关注

发布于: 2021 年 06 月 01 日

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题意简洁明了。我们解决这个问题，需要熟练应用栈这种数据结构。
栈这种数据结构，具有后进先出（last in first out）的性质。
在 Java 中，我常常使用 Deque 来实现 Stack 的功能。 Deque 是双端队列，使用起来更加方便。
具体到这个题目，我自定义了 StackNode 数据结构，其中存储了当前的节点值和当前节点值在 Stack 中的最小值。从而满足题目要求。

AC 代码

class MinStack {
    Deque<StackNode> stack;
    /** initialize your data structure here. */    public MinStack() {        stack = new ArrayDeque<>();    }
    public void push(int x) {        StackNode node;        if (stack.isEmpty()) {            node = new StackNode(x, x);        } else {            node = new StackNode(x, Math.min(x,stack.peek().getMinVal()));        }        stack.push(node);    }
    public void pop() {        stack.pop();    }
    public int top() {        return stack.peek().getCurrentVal();    }
    public int min() {        return stack.peek().getMinVal();    }}
class StackNode {    Integer currentVal;    Integer minVal;
    public StackNode(Integer currentVal, Integer minVal) {        this.currentVal = currentVal;        this.minVal = minVal;    }
    public Integer getCurrentVal() {        return currentVal;    }
    public void setCurrentVal(Integer currentVal) {        this.currentVal = currentVal;    }
    public Integer getMinVal() {        return minVal;    }
    public void setMinVal(Integer minVal) {        this.minVal = minVal;    }}/** * 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.min(); */

复制代码

总结

上述代码的时间复杂度是 O(1), 空间复杂度是 O(n)
算法题目需要多练习，不仅要看，也要写，才能有更好的收获！
坚持每日一题，加油！

发布于: 2021 年 06 月 01 日阅读数: 9

原文链接:【http://xie.infoq.cn/article/d433e15cfa08d83448b27390a】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】包含 min 函数的栈 Java 题解

题目描述

思路分析

AC 代码

总结

HQ数字卡

评论