155. Min Stack (Easy)
https://leetcode.com/problems/min-stack/
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.
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.
Solutions
1.
class MinStack {
Stack<Integer> stack;
Queue<Integer> queue;
public MinStack() {
stack = new Stack<>();
queue = new PriorityQueue<>();
}
public void push(int x) {
stack.push(x);
queue.offer(x);
}
public void pop() {
int value = stack.pop();
queue.remove(Integer.valueOf(value));
}
public int top() {
return stack.peek();
}
public int getMin() {
return queue.peek();
}
}
2.
class MinStack {
Stack<Integer> stack;
Stack<Integer> min;
public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (min.isEmpty() || x <= min.peek()) {
min.push(x);
}
}
public void pop() {
int value = stack.pop();
if (min.peek() == value) {
min.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min.peek();
}
}
3.
class MinStack {
class ListNode {
int value = 0;
ListNode next = null;
public ListNode(int v) {
value = v;
}
}
ListNode stack;
ListNode queue;
public MinStack() {
stack = new ListNode(-1);
queue = new ListNode(-1);
}
public void push(int x) {
ListNode n1 = new ListNode(x);
n1.next = stack.next;
stack.next = n1;
ListNode n2 = new ListNode(x);
if (queue.next == null) {
queue.next = n2;
} else {
ListNode ptr = queue;
while (ptr.next != null) {
if (ptr.next.value < x) {
ptr = ptr.next;
continue;
}
n2.next = ptr.next;
ptr.next = n2;
break;
}
}
}
public void pop() {
ListNode val = null;
if (stack.next != null) {
val = stack.next;
stack.next = stack.next.next;
}
if (val != null) {
ListNode ptr = queue;
while (ptr.next != null) {
if (ptr.next.value != val.value) {
ptr = ptr.next;
continue;
}
ptr.next = ptr.next.next;
break;
}
}
}
public int top() {
if (stack != null) {
return stack.next.value;
}
return 0;
}
public int getMin() {
if (queue.next != null) {
return queue.next.value;
}
return 0;
}
}