栈
汉诺塔问题
最小栈
最小栈
额外空间\(O(N)\)
辅助栈解法
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
int x = minStack.peek();
xStack.push(val);
minStack.push(x < val ? x:val);
}
public void pop() {
minStack.pop();
xStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
双值域节点链表解法
class MinStack {
class Node{
int val;
int min;
Node next;
public Node(){
}
public Node(int val, int min, Node next){
this.val = val;
this.min = min;
this.next = next;
}
}
Node head;
public MinStack(){
}
public void push(int val){
if(head == null){
head = new Node(val, val, null);
} else {
Node cur = new Node(val, (val < head.min?val:head.min), head);
head = cur;
}
}
public void pop(){
head = head.next;
}
public int top(){
return head.val;
}
public int getMin(){
return head.min;
}
}
无额外空间
差分解法