155. Min Stack
Tags: ‘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.
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.
Solution
用Linkedlist实现Stack， 同时每个节点存放min记录stack到当前位置时的最小值
class MinStack {
private Node head;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
if (head == null) {
this.head = new Node(x, x, null);
} else {
this.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;
}
class Node {
private int val;
private int min;
private Node next;
public Node(int val, int min) {
this(val, min, null);
}
public Node(int val, int min, Node node) {
this.val = val;
this.min = min;
this.next = node;
}
}
}