Version: Next
155.minStack
难度 简单
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
pop、top和getMin操作总是在 非空栈 上调用。
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object. void push(val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack.
使用两个栈
- 一个正常栈，另一个记录每个状态下正常栈中的最小值
- 他们之间数量、状态都一一对应
- 在添加元素时
public class _155最小栈 {
private Stack<Integer> stack;
private Stack<Integer> minStack;
/**
* initialize your data structure here.
*/
public _155最小栈() {
this.stack = new Stack<>();
this.minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty())
minStack.push(val);
else
minStack.push(Math.min(val, minStack.peek()));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
链表法
- 构建一个链表，其中的链表节点，存储两个值，
当前新值和当前最小值- 采用
头插法，就可以模拟栈
public class _155最小栈 {
private MinStackListNode head;
/**
* initialize your data structure here.
*/
public _155最小栈() {
head = new MinStackListNode(Integer.MAX_VALUE, Integer.MAX_VALUE, null);
}
public void push(int val) {
head = new MinStackListNode(val, Math.min(val, head.minVal), head);
}
public void pop() {
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.minVal;
}
private static class MinStackListNode {
public int val;
public int minVal;
public MinStackListNode next;
public MinStackListNode() {
}
public MinStackListNode(int val, int minVal, MinStackListNode next) {
this.val = val;
this.minVal = minVal;
this.next = next;
}
}
}