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.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.解题 使用2个栈s1，s2: s1负责正常栈的储存。 s2储存每次出现最小的数的。 这样当s1删除到最小的数的时候，s2也删除栈顶的数。这样可以保证s2的栈顶一直是当前最小数。因为即使s1里面包含的当前第二小的数而s2不包含，需要用到这个第二小的数的时候，这个数早就被删除了。比如： s1: 栈顶(2->1->3->4); s2: 栈顶(1->3->4); 当删除1时，2早就不在s1中，所以接下来最小数是3。 class MinStack { Stack<Integer> element = new Stack<Integer>(); Stack<Integer> minStack = new Stack<Integer>(); public void push(int x) { element.add(x); if (minStack.isEmpty() || x <= minStack.peek()) { minStack.add(x); } } public void pop() { if(element.isEmpty()) return; if (element.peek().equals(minStack.peek())) { minStack.pop(); } element.pop(); } public int top() { return element.peek(); } public int getMin() { return minStack.peek(); } }reference： 作者：黑山老水 链接：https://www.jianshu.com/p/67f2c14accda 來源：简书 简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。
转载于:https://www.cnblogs.com/hygeia/p/10090163.html
相关资源：JAVA上百实例源码以及开源项目