当前位置 博文首页 > Liu，：Leetcode——最小栈（使用链表辅助）
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
解法一：
让我们自定义一个栈，有push，pop，top，min四个函数。这题和官方的Stack相比就多了一个min函数。栈的实现我们可以使用链表，先来定义一个链表类
class ListNode {
public int val;
public int min;//最小值
public ListNode next;
public ListNode(int val, int min, ListNode next) {
this.val = val;
this.min = min;
this.next = next;
}
}
这里对链表的操作永远都是链表的头，假如往栈中加入3→2→5→4，画个图来看一下使用链表怎么操作的
class ListNode {
public int val;
public int min;//最小值
public ListNode next;
public ListNode(int val, int min, ListNode next) {
this.val = val;
this.min = min;
this.next = next;
}
}
class MinStack {
//链表头，相当于栈顶
private ListNode head;
//压栈，需要判断栈是否为空
public void push(int x) {
if (empty())
head = new ListNode(x, x, null);
else
head = new ListNode(x, Math.min(x, head.min), head);
}
//出栈，相当于把链表头删除
public void pop() {
if (empty())
throw new IllegalStateException("栈为空……");
head = head.next;
}
//栈顶的值也就是链表头的值
public int top() {
if (empty())
throw new IllegalStateException("栈为空……");
return head.val;
}
//链表中头结点保存的是整个链表最小的值，所以返回head.min也就是
//相当于返回栈中最小的值
public int getMin() {
if (empty())
throw new IllegalStateException("栈为空……");
return head.min;
}
//判断栈是否为空
private boolean empty() {
return head == null;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
解法二：
使用两个栈，一个存储最小值，一个存储所有
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 x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
