LeetCode 155. Min Stack 题解

  题目链接：点击打开链接

  思路：本题的push、pop、top都可以直接使用java自带的stack实现。关键在于如何实现getMin（）方法。

             使用两个栈，第一个栈正常保存全部数据，第二个栈只保存数据中的“不升序”序列，这其中的奥妙需要自行体会一下.....

Java 参考代码如下：

import java.util.Stack;

public class MinStack {

	Stack<Integer> stack;
	Stack<Integer> minStack;

	/** initialize your data structure here. */
	public MinStack() {
		stack = new Stack<Integer>();
		minStack = new Stack<Integer>();
	}

	public void push(int x) {
		stack.push(x);
		// 第二个条件之所以是<= 而不是 <， 是因为对于push(0,3,0,2)  pop(2,0)这种情况，
		// 如果是<号，则获取最小值会出错
		if (minStack.isEmpty() || x <= minStack.peek()) {
			minStack.push(x);
		}
	}

	public void pop() {
		int popNum = stack.peek();
		if (!stack.isEmpty()) {
			stack.pop();
		}
		// 第二个判断条件，之所以是==而不是 <=，是因为stack.peek不可能比minStack.peek小，
		// 否则在该栈顶元素push入栈的时候，它就会被压到minStack的栈顶....
		if (!minStack.isEmpty() && popNum == minStack.peek()) {
			minStack.pop();
		}
	}

	public int top() {
		return stack.isEmpty()?0:stack.peek();
	}

	public int getMin() {
		return minStack.isEmpty()?0:minStack.peek();
	}
}