Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- 1. push(x) — Push element x onto stack.
- 2. pop() — Removes the element on top of the stack.
- 3. top() — Get the top element.
- 4. getMin() — Retrieve the minimum element in the stack.
Example 1:
Constraints:
- Methods
pop ,top andgetMin operations will always be called on non-empty stacks.
Solution
To get min element in constant time, we need two collections to store one for the actual data and other for min value.
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.ArrayList; import java.util.List; class MinStack { /** initialize your data structure here. */ List<Integer> list; List<Integer> min; public MinStack() { list=new ArrayList<Integer>(); min=new ArrayList<Integer>(); } public void push(int x) { list.add(x); if(min.size()==0) min.add(x); else { min.add(Math.min(min.get(min.size()-1),x)); } } public void pop() { min.remove(min.size()-1); list.remove(list.size()-1); } public int top() { return list.get(list.size()-1); } public int getMin() { return min.get(min.size()-1); } } public class MinStackTest { public static void main(String[] args) { MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); System.out.println(minStack.getMin()); minStack.pop(); System.out.println(minStack.top()); System.out.println(minStack.getMin()); } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.