[LintCode] Min Stack [花枝春满]

java 4 2016-02-29 13:03
女装

Problem

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Example

push(1)
pop() // return 1
push(2)
push(3)
min() // return 2
push(1)
min() // return 1

Note

min operation will never be called if there is no number in the stack.
注意在push()里的条件,minstack.peek() >= number,加上等号,为什么?我也不知道,不过多push进去一个相同的元素,何伤乎?
第二点:

if (!stack.isEmpty()) {
                int element = stack.peek();
                if (minstack.peek() == element) {
                    minstack.pop();
                }
            }

这里面很奇怪,直接写if (minstack.peek() == stack.peek()),就会报错。
改成:

if (Integer.valueOf(minstack.peek()) == Integer.valueOf(stack.peek()))

也会报错。
所以是.valueOf()的问题吗?那么不用==,换成.equals()看看:

if (minstack.peek().equals(Integer.valueOf(stack.peek()))),

这就对了。
那么改成 minstack.peek().equals(stack.peek())也就一定是对的了。
再试试别的,parseInt(),各种不对,用.equals()都不可以,完全不对。
那么,试试.intValue(),又对了,用==都可以。

if (minstack.peek().intValue() == stack.peek().intValue())

确然是对的。
所以说去研究一下Integer的各种函数吧。

valueOf(String) returns a new java.lang.Integer, which is the object representative of the integer,
whereas parseInt(String) returns a primitive integer type int.
intValue is an instance method whereby parseInt is a static method.
Moreover, Integer.parseInt(s) can take primitive datatype as well.

Solution

public class MinStack {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> minstack = new Stack<Integer>();
    public MinStack() {

    }

    public void push(int number) {
        stack.push(number);
        if (minstack.isEmpty() || minstack.peek() >= number) {
            minstack.push(number);
        }
    }

    public int pop() {
    //根本无需判断stack是否非空,直接这样写!
        if (stack.peek().equals(minstack.peek())) { 
            minstack.pop();
        }
        return stack.pop();
    }

    public int min() {
        return minstack.peek();
    }
}
女装
文章评论