package cn.edu.xidian.sselab.stack;
import java.util.Stack;/** * * @author zhiyong wang * title: Min Stack * content: * Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. * * push(x) -- Push element x onto stack. * pop() -- Removes the element on top of the stack. * top() -- Get the top element. * getMin() -- Retrieve the minimum element in the stack. * 一开始没弄懂这个题的意思，现在搞懂了：最小栈相当于一个辅助栈，用来存储另一一个栈的最小元素的集合： * 具体可以这样理解，因为push(x),pop(),top()都可以在O(1)时间内完成，但是getMin()获取最小值的这种操作就不能在O(1)时间内完成 * 所以这里借助了最小栈的概念 * （1）push的时候，stack肯定会存放数据，如果最小栈是空的或者最小栈的栈顶元素小于要存放数据元素，最小栈也会存放数据【这样最小栈一直维护着一个从栈顶到栈底是由小到大排序的】，否则最小栈不存放数据 * （2）pop的时候，如果stack是空的则不管，如果不是空的，则弹出栈顶元素，如果最小栈不是空的，并且栈顶元素与stack栈弹出的元素相等，那么最小栈也需要弹出栈顶元素 * （3）top的时候，观察stack是否为空，如果为空则不管，如果不为空，则查看栈顶元素，与最小栈没有关系 * （4）getMin的时候，这个时候跟stack是没有关系的，如果最小栈不为空，在查看栈顶元素 * * */public class MinStack { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> minStack = new Stack<Integer>(); public void push(int x){ stack.push(x); if(minStack.isEmpty() || minStack.peek() >= x) minStack.push(x); } public void pop(){ if(stack.isEmpty()) return ; int temp = stack.pop(); if(!minStack.isEmpty() && temp == minStack.peek()) minStack.pop(); } public int top(){ return stack.peek(); } public int getMin(){ return minStack.peek(); }}这个地方参考了讲解：http://www.tuicool.com/articles/zARfAj这道题是关于栈的题目，实现一个栈的基本功能，外加一个获得最小元素的操作。正常情况下top，pop和push操作都是常量时间的，而主要问题就在于这 个getMin上面，如果遍历一遍去找最小值，那么getMin操作就是O(n)的，既然出出来了这道题就肯定不是这么简单的哈。比较容易想到就是要追溯 这个最小值，在push的时候维护最小值，但是如果pop出最小值的时候该如何处理呢，如何获得第二小的值呢？如果要去寻找又不是常量时间了。解决的方案 是再维护一个栈，我们称为最小栈，如果遇到更小的值则插入最小栈，否则就不需要插入最小栈（注意这里正常栈是怎么都要插进去的）。这里的正确性在于，如果 后来得到的值是大于当前最小栈顶的值的，那么接下来pop都会先出去，而最小栈顶的值会一直在，而当pop到最小栈顶的值时，一起出去后接下来第二小的就 在pop之后最小栈的顶端了。如此push时最多插入两个栈一个元素，是O(1)，top是取正常栈顶，自然是O(1)，而pop时也是最多抛出两个栈的 栈顶元素，O(1)。最后getMin只需要peek最小栈顶栈顶即可，所以仍是O(1)，实现了所有操作的常量操作，空间复杂度是O(n)，最小栈的大 小。代码如下