VietMX Staff asked 3 years ago
Problem
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.
Using a linked list store the current minimum value. When you add a new number it looks at the previous min and changes the current min to the current value if the current value is lower. Note, each node stores the min value at or below it so we don’t need to recalculate min on pop.
Implementation
class MinStack {
private class Node {
int val;
int min;
Node next;
private Node(int val, int min) {
this(val, min, null);
}
private Node(int val, int min, Node next) {
this.val = val;
this.min = min;
this.next = next;
}
}
private Node head;
public void push(int x) {
if(head == null)
head = new Node(x, x);
else
head = new Node(x, Math.min(x, head.min), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
}