本文共 1682 字，大约阅读时间需要 5 分钟。
题目描述：
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.
设计一个最小栈，支持入栈，出栈，获取栈顶元素，获取栈最小值，要求时间复杂度0(1).
Stack(栈)是First in-Last out的数据结构。如果不考虑时间复杂度，实现题目的要求都比较简单，现在限定了不超过常量时间O（1），
就不能用简单的排序过滤实现了。另外，栈顶(top)指的是允许操作数据的一端，要与堆栈中高低地址不同的栈顶和栈底区别开来，以前我经常搞混。
public class MinStack { //声明数据栈 private Stack elementsStack=new Stack (); //声明辅助栈 private Stack supportStack=new Stack (); /** * 考虑到时间复杂度的需求，添加一个辅助栈， * 每次入栈时将元素分别存入数据栈和辅助栈， * 辅助栈中的数据始终保持最小值在栈顶，需要获取最小值时，直接Peek()辅助栈即可。 */ public static void main(String[] args){ MinStack minStack=new MinStack(); //以下测试用例 minStack.push(0); minStack.push(1); minStack.push(0); System.out.print(minStack.getMin()); minStack.pop(); System.out.print(minStack.getMin()); } public void push(int x) { //始终保持辅助栈顶是最小元素 if(supportStack.empty() || x <= supportStack.peek()){ supportStack.push(x); } elementsStack.push(x); } public void pop() { //更新辅助栈 if(elementsStack.peek().equals(supportStack.peek())){ supportStack.pop(); } elementsStack.pop(); } public int top() { return elementsStack.peek(); } public int getMin() { //辅助栈 return supportStack.peek(); }} 提交，可以AC.
本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/4111369.html，如需转载请自行联系原作者