题目：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
方法一：双栈法
思路：
在push的时候就将最小值记录下来，由于栈后进先出的特殊性，我们可以构造一个单调栈，保证栈内元素都是递增的，栈顶元素就是当前最小的元素。
具体做法：
step 1：使用一个栈s1记录进入栈的元素，正常进行push、pop、top操作。
step 2：使用另一个栈s2记录每次push进入的最小值。
step 3：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素也就是min再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶。
如果s1 push的不是最小，为什么要重复在s2加入之前的min ？
因为存在pop()方法，当s1 pop时，如果pop的刚好就是是min，那么s2也应该将min弹出。 所以将s2和s1的个数保持同步就比较方便，所以即使push的不是最小，也要更新s2。
public class Solution {
//双栈法
Stack<Integer> s1=new Stack<>();
Stack<Integer> s2=new Stack<>();
public void push(int node) {
s1.push(node);
if(s2.isEmpty()||node<s2.peek()){ //如果新加入的比s2栈顶的更小则添加至s2
s2.push(node);
}else{ //如果新加入的没有s2栈顶小，则把s2栈顶的数重复添加至s2
s2.push(s2.peek()); //重复压入min
}
}
//当s1弹出时，s2也要弹出，不然s1中的min变了 而s2还没变！ 或者判断s1弹出的是否是min，是则弹出s2
public void pop() {
s1.pop();
s2.pop();
}
public int top() {
return s1.peek();
}
public int min() {
return s2.peek();
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89338.html
