1、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.
codes below
class MinStack {
private int size = 0;
private Node head = null;
class Node {
int val;
// every node contains min value at the moment it was pushed
int min;
Node next;
Node(int v, int m) {val = v; min = m;}
}
public void push(int x) {
int curMin = getMin();
int newMin = x < curMin ? x : curMin;
Node n = new Node(x, newMin);
n.next = head;
head = n;
size++;
}
public void pop() {
if (size <= 0)
return;
head = head.next;
size--;
}
public int top() {
if (size <= 0)
return Integer.MAX_VALUE;
return head.val;
}
public int getMin() {
if (size <= 0)
return Integer.MAX_VALUE;
return head.min;
}}
这个使用ListNode的方法我还是没见过的。果然脑洞大开啊！
