中国宁波网_搜索更多网页内容_会员制营销_台州seo快速排名

在O（N）时间复杂度内找出最小值：

1. 创建两个栈
2. 当普通栈只有一个数据时，把该数据放入最小栈
3. 往普通栈放入数据时，把要放入的数据和最小栈的栈顶数据相比较，若要放入的数据比最小栈的栈顶数据小，则把该数据放入最小栈
4. 需要找栈的最小值时，直接取栈顶数据

入栈（push）操作小结：

• 普通栈一定要放，最小栈放的原则是：
• 最小栈为空，放
• 若当前元素比最小栈栈顶元素小，则放

问题：如果要放的元素  等于  最小栈栈顶元素，要放吗？

答：要放

理由：这涉及到出栈（pop）操作，如果pop把最上面的-2出出去了，最小栈栈顶的-2也会出去，但是实际上普通栈内还有一个最小的值-2，但最小栈栈顶已经不是-2了

 出栈（pop）操作小结：

• 需要判断  出栈的元素  和 最小栈栈顶的元素 是否相同，相同则最小栈也要出栈

import java.util.Stack;//最小栈代码实现
public class Minstack {public Stack<Integer> stack;public Stack<Integer> minStack1;public Minstack(){
stack=new Stack<>();
minStack1=new Stack<>();}public void push(int val){//入栈操作
stack.push(val);//由于普通栈是一定要放的if(minStack1.empty()){//如果最小栈是空的，则往里放minStack1.push(val);}else {//当最小栈不为空时，放入的元素要和最小栈的栈顶元素去比较，小于等于栈顶则放入最小栈int peekVal=minStack1.peek();//先拿到最小栈栈顶元素if(val<=peekVal){minStack1.push(val);}}}public void pop(){//出栈操作if(stack.empty()){//如果栈为空，无法出栈return;}//如果栈不为空，先判断两栈顶元素是否相同，相同则最小栈的栈顶也出出去int popVal=stack.pop();if(popVal==minStack1.peek()){minStack1.pop();}}public int top(){//获取普通栈的栈顶元素if(stack.empty()){//如果栈为空，无法出栈，此时应该要报一个异常return -1;}return stack.peek();}public int getMin(){if(minStack1.empty()){//如果栈为空，无法出栈，此时应该要报一个异常return -1;}return minStack1.peek();}
}