X

LEETCODE 155. Min Stack 解题思路分析

题目大意:

最小栈

设计一个支持 pushpoptop 操作,并能在常数时间内检索到最小元素的栈。

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

示例:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出:
[null,null,null,null,-3,null,0,-2]
解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

提示:

  • poptopgetMin 操作总是在 非空栈 上调用。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=155

解题思路分析:

这道题的解法有很多,我比较推荐使用链表的方式。我们将每次push入栈的数值以链表的方式存储,链表的每个节点中,记录下该节点的值,当前链表中的最小值,以及当前节点的前一个节点。

解题时,我们定义一个全局Node节点变量代表当前链表的尾节点(初始为空)。当调用到push方法时,如果Node为空,我们新建一个Node节点对象赋值到尾节点,该节点的值以及链表最小值均为当前push的数值。反之如果当前链表的尾节点Node不为空,我们同样需要新建一个节点对象current,current值为当前push值,current最小值为当前push值,与节点Node中的最小值中更小的一方。接下来将current的前节点设置为Node节点,并同时将current变为链表尾节点。

另外调用到pop方法时,我们只要将Node替换为Node的前节点即可。

top方法的返回值为当前尾节点Node的数值。

getMin方法的返回值为当前尾节点Node的最小值。

实现代码:

class Node{
    int val;
    int min;
    Node previous; 
    Node(int v, int m){
        val=v;
        min=m;
    }
}
Node node;
/** initialize your data structure here. */public MinStack() {

}

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

public void pop() {
    node=node.previous;
}

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

public int getMin() {
    return node.min;
}

本题解法执行时间为5ms。

Runtime: 5 ms, faster than 55.97% of Java online submissions for Min Stack.

Memory Usage: 45.7 MB, less than 5.08% of Java online submissions for Min Stack.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-155-min-stack-解题思路分析/
Categories: leetcode
kwantong: