题目大意：
最小栈
设计一个支持 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操作总是在 非空栈 上调用。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=155
解题思路分析：
这道题的解法有很多，我比较推荐使用链表的方式。我们将每次push入栈的数值以链表的方式存储，链表的每个节点中，记录下该节点的值，当前链表中的最小值，以及当前节点的前一个节点。
解题时，我们定义一个全局Node节点变量代表当前链表的尾节点（初始为空）。当调用到push方法时，如果Node为空，我们新建一个Node节点对象赋值到尾节点，该节点的值以及链表最小值均为当前push的数值。反之如果当前链表的尾节点Node不为空，我们同样需要新建一个节点对象current，current值为当前push值，current最小值为当前push值，与节点Node中的最小值中更小的一方。接下来将current的前节点设置为Node节点，并同时将current变为链表尾节点。
另外调用到pop方法时，我们只要将Node替换为Node的前节点即可。
top方法的返回值为当前尾节点Node的数值。
getMin方法的返回值为当前尾节点Node的最小值。
实现代码：
class Node{
int val;
int min;
Node previous;
Node(int v, int m){
val=v;
min=m;
}
}
Node node;
/** initialize your data structure here. */public MinStack() {
}
public void push(int x) {
if(node==null){
node=new Node(x, x);
}else{
Node n=new Node(x, Math.min(x,node.min));
n.previous=node;
node=n;
}
}
public void pop() {
node=node.previous;
}
public int top() {
return node.val;
}
public int getMin() {
return node.min;
} 本题解法执行时间为5ms。
Runtime: 5 ms, faster than 55.97% of Java online submissions for Min Stack.
Memory Usage: 45.7 MB, less than 5.08% of Java online submissions for Min Stack.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-155-min-stack-解题思路分析/