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();	}}