【算法描述】
入栈规则 假设当前入栈数据为 newData ，先将其压入 dataStack ，然后判断 minStack 是否为空；如果为空，则把 newData 压入 minStack ；如果不为空，则比较 newData 与 minStack 的栈顶元素哪一个更小；如果 newData 更小或者两者相等，则将 newData 压入 minStack ；如果 minStack 中栈顶元素更小，则把 minStack 栈顶元素重复压入 minStack 栈顶。【举个栗子】 依次入栈3、4、5、1、2、1的过程中，dataStack 和 minStack 变化如图所示：
出栈规则 在 dataStack 弹出栈顶数据记为 value ，minStack 也对应弹出栈顶元素。返回value。
获取当前栈中的最小值操作 由上述描述可知，minStack 栈中的栈顶元素始终记录着 dataStack 栈的最小值，所以只需返回 minStack 的栈顶元素即可。
1import java.util.Stack; 2 3public class MyStack1 { 4 private Stack<Integer> dataStack; 5 private Stack<Integer> minStack; 6 7 public MyStack1() { 8 dataStack = new Stack<Integer>(); 9 minStack = new Stack<Integer>(); 10 } 11 12 //入栈 13 public void push(int newData) { 14 dataStack.push(newData); 15 if(this.minStack.isEmpty() || newData < this.getMin()) { 16 minStack.push(newData); 17 } else { 18 minStack.push(this.minStack.peek()); 19 } 20 } 21 22 //出栈 23 public int pop() { 24 if (dataStack.isEmpty()) { 25 throw new RuntimeException("Your Stack is empty!"); 26 } 27 this.minStack.pop(); 28 return this.dataStack.pop(); 29 } 30 31 //获得栈中的最小值 32 public int getMin() { 33 if(this.minStack.isEmpty()) { 34 throw new RuntimeException("Your minStack is empty!"); 35 } 36 return this.minStack.peek(); 37 } 38 39}时间复杂度为 O(1),空间复杂度为 O（n），用于 minStack 的空间开销 能否设计空间复杂度更优的算法呢？请看实现方案二。
【算法描述】
入栈规则 假设当前入栈数据为 newData ，先将其压入 dataStack ，然后判断 minStack 是否为空；如果为空，则把 newData 压入 minStack ；如果不为空，则比较 newData 与 minStack 的栈顶元素哪一个更小；如果 newData 更小或者与 newData 相等，则将 newData 压入 minStack ；如果 minStack 中栈顶元素更小，则 minStack 不压入任何内容。【举个栗子】 依次入栈3、4、5、1、2、1的过程中，dataStack 和 minStack 变化如图所示：
出栈规则 在 dataStack 弹出栈顶数据记为 value ，然后比较当前 minStack 的栈顶元素和 value 哪一个更小。由上文的入栈规则可知，minStack 的栈顶元素既是 minStack 栈的最小元素，也是当前 dataStack 栈中的最小元素，因此 value 只可能大于或等于 minStack 的栈顶元素，不会出现 value 小于 minStack 的栈顶元素。当 value 等于 minStack 的栈顶元素，则弹出 minStack 中的栈顶元素，当 value 大于 minStack 元素的栈顶元素，minStack 不弹出栈顶元素，组后返回 value。 获取当前栈中的最小值操作 由上述描述可知，minStack 栈中的栈顶元素始终记录着 dataStack 栈的最小值，所以只需返回 minStack 的栈顶元素即可。 1public class MyStack2 { 2 private Stack<Integer> dataStack; 3 private Stack<Integer> minStack; 4 5 public MyStack2() { 6 dataStack = new Stack<Integer>(); 7 minStack = new Stack<Integer>(); 8 } 9 10 //入栈 11 public void push(int newData) { 12 dataStack.push(newData); 13 if(minStack.isEmpty() || newData <= this.getMin()) { 14 minStack.push(newData); 15 } 16 } 17 18 //出栈 19 public int pop() { 20 if (dataStack.isEmpty()) { 21 throw new RuntimeException("Your Stack is empty!"); 22 } 23 int value = this.dataStack.peek(); 24 if(value == this.getMin()) { 25 this.minStack.pop(); 26 } 27 return value; 28 } 29 30 //获取栈中最小值 31 public int getMin() { 32 if(this.minStack.isEmpty()) { 33 throw new RuntimeException("Your Stack is empty!"); 34 } 35 return minStack.peek(); 36 } 37}时间复杂度为 O(1)，空间复杂度为 O（n），用于 minStack 的开销。 优化点：当算法运行过程中很少遇到“新的最小值或相等”情况时，，该算法的空间利用效率将大大改善！
