法一:使用辅助栈
一个栈正常存,另一个存最小值
class MinStack {
Deque<Integer>stack;
Deque<Integer>minstack;
public MinStack() {
stack = new LinkedList<>();
minstack = new LinkedList<>();
}
public void push(int val) {
stack.push(val);
if(minstack.isEmpty()||val <= minstack.peek()){
minstack.push(val);
}
}
public void pop() {
Integer pop = stack.pop();
if(pop.equals(minstack.peek())){
minstack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minstack.peek();
}
}
法二:创建新的Node节点,Node节点包括val和min
class MinStack {
private static class Node{
int value;
int min;
Node next;
Node(int x,int min){
this.value = x;
this.min = min;
next = null;
}
}
private Deque<Node>stack;
public MinStack() {
stack = new LinkedList<>();
}
public void push(int val) {
if(stack.isEmpty()){
stack.push(new Node(val,val));
}
else{
stack.push(new Node(val,Math.min(stack.peek().min,val)));
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek().value;
}
public int getMin() {
return stack.peek().min;
}
}
自己实现栈,可以用单链表的头插法
class MinStack {
class Node{
int value;
int min;
Node next;
Node(int x, int min){
this.value=x;
this.min=min;
next = null;
}
}
Node head;
//每次加入的节点放到头部
public void push(int x) {
if(null==head){
head = new Node(x,x);
}else{
//当前值和之前头结点的最小值较小的做为当前的 min
Node n = new Node(x, Math.min(x,head.min));
n.next=head;
head=n;
}
}
public void pop() {
if(head!=null)
head =head.next;
}
public int top() {
if(head!=null)
return head.value;
return -1;
}
public int getMin() {
if(null!=head)
return head.min;
return -1;
}
}
作者:windliang
链接:https://leetcode.cn/problems/min-stack/solutions/42521/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。