155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
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.
package leetcode.easy; import java.util.Stack; public class MinStack { @org.junit.Test public void test() { MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); System.out.println(minStack.getMin());// --> Returns -3. minStack.pop(); System.out.println(minStack.top());// --> Returns 0. System.out.println(minStack.getMin());// --> Returns -2. } private Stack<Integer> stack = new Stack<Integer>(); private Stack<Integer> min_stack = new Stack<Integer>(); /** initialize your data structure here. */ public MinStack() { } public void push(int x) { stack.push(x); if (min_stack.isEmpty() || ((!min_stack.isEmpty()) && x <= min_stack.peek())) { min_stack.push(x); } } public void pop() { if (!stack.isEmpty()) { if (stack.peek().equals(min_stack.peek())) { min_stack.pop(); } stack.pop(); } } public int top() { if (!stack.isEmpty()) { return stack.peek(); } return Integer.MIN_VALUE; } public int getMin() { if (!min_stack.isEmpty()) { return min_stack.peek(); } return Integer.MIN_VALUE; } } /** * Your MinStack object will be instantiated and called as such: MinStack obj = * new MinStack(); obj.push(x); obj.pop(); int param_3 = obj.top(); int param_4 * = obj.getMin(); */
原文:https://www.cnblogs.com/denggelin/p/11670183.html