Difficulty : Easy
Related Topics : Stack、Design
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.
Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks.
- mine
- Java
Runtime: 3 ms, faster than 100.00%, Memory Usage: 41.6 MB, less than 12.63% of Java online submissions
LinkedList<Node> list; int min; public MinStack() { list = new LinkedList<>(); min = Integer.MAX_VALUE; } public void push(int x) { min = Math.min(x, min); list.add(new Node(x, min)); } public void pop() { list.removeLast(); if(list.size() > 0){ min = list.getLast().m; }else{ min = Integer.MAX_VALUE; } } public int top() { return list.getLast().val; } public int getMin() { return list.getLast().m; } class Node { int val; int m; public Node(int val, int m) { this.val = val; this.m = Math.min(m, val); } }
- Java