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. 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.
题意：
请设计一个栈结构，支持 push、pop、top以及getMin操作，且每个操作的时间复杂度都是 O(1)。
思路：
维护一个单调栈minStack
code
1 class MinStack { 2 3 /** initialize your data structure here. */ 4 Stack<Integer> s ; 5 Stack<Integer> minStack ; 6 7 public MinStack() { 8 s = new Stack<>(); 9 minStack = new Stack<>(); 10 } 11 12 public void push(int x) { 13 s.push(x); 14 int minValue = minStack.isEmpty() ? x: Math.min(minStack.peek(), x); 15 minStack.push(minValue); 16 17 } 18 19 public void pop() { 20 s.pop(); 21 minStack.pop(); 22 } 23 24 public int top() { 25 return s.peek(); 26 27 28 } 29 30 public int getMin() { 31 return minStack.peek(); 32 } 33 }
转载于:https://www.cnblogs.com/liuliu5151/p/10873295.html
