leetcode-155-最小栈
思路:此题关键意义在于实现寻找最小值O(1)算法,所以关键在于每次压栈时可以记录此时的最小值,并且可以记录每一次的
方法一:
//取巧做法,类似于两个栈
class MinStack {
private Stack<Integer> s;
public MinStack() {
s = new Stack<Integer>();
}
public void push(int val) {
if(s.isEmpty()){
s.push(val);
s.push(val);
}else{
int min=s.peek();
if(val<min){
min=val;
}
s.push(val);
s.push(min);
}
}
public void pop() {
s.pop();
s.pop();
}
public int top() {
//因为stack类继承了Vector类所以可以使用vector的方法,存储时从0开始
return s.get(s.size()-2);
}
public int getMin() {
return s.peek();
}
}
方法二:链表写法,比较好,类似于头插法
class MinStack {
private class Node{
int min;
int val;
Node next;
Node(int val,int min,Node next){
this.val=val;
this.min=min;
this.next=next;
}
}
private Node head;
public MinStack() {
}
public void push(int val) {
if(head==null){
head =new Node(val,val,null);
}else{
head=new Node(val,Math.min(head.min,val),head);
}
}
public void pop() {
head=head.next;
}
public int top() {
int x=head.val;
return x;
}
public int getMin() {
return head.min;
}
}