2014-11-14

Leetcode-MinStack

Navigation

先给出题目的地址吧:https://oj.leetcode.com/problems/min-stack/

昨天一个同学问了我这道题，回去就做了一下。
初看这道题，好像并不难，push、pop、top都是栈的基本操作，getMin好像不太好搞。
首先想到的是用一个变量min记录一下栈的最小值，每次压栈的时候比较压栈元素和min的大小，更新min值。
这个想法好像还不错，于是搞之，一交WA了。
仔细一想，如果当前的min值是栈顶的值，把栈顶的值pop之后，这个min值就不再是栈中最小的值了，此时最小值变成了栈中的次小值了。
自然就想到，能不能再记住次小值呢？当然是可以的。可是这样问题又来了，如果次小值再被弹出呢？那就不行了。
最后，想到的做法是，每次压栈的时候都去记住当前栈的最小值，把它记在栈顶上，这样栈顶就始终保存这当前栈的最小值。
于是，开开心心的去写代码，交之，TMD，居然告诉我MLE。
你大爷啊，这让我如何是好？
看了半天代码，实在没有内存需要优化的地方了。最后在内部类前面加了个static，然后就过了。
他就这么过了，加了个static为啥就过了呢？有点疑惑。

package com.tcheung;

import java.util.Stack;

/**
 * MinStack
 *
 * @author: zhangteng
 * @time: 2014/11/14 21:12
 */
class MinStack {

    static class Element {
        int val, min;
        public Element(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }

    private int min;

    private Stack<Element> stack = new Stack<Element>();

    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
        } else {
            min = Math.min(stack.peek().min, x);
        }
        stack.push(new Element(x, min));
    }

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

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

    public int getMin() {
        return stack.peek().min;
    }
}

leetcode, java