(lintcode)第12题带最小值操作的栈

要求：实现一个带有取最小值min方法的栈，min方法将返回当前栈中的最小值。你实现的栈将支持push，pop 和 min 操作，所有操作要求都在O(1)时间内完成。

注意事项：如果堆栈中没有数字则不能进行min方法的调用。

样例：如下操作：push(1)，pop()，push(2)，push(3)，min()， push(1)，min() 返回 1，2，1

思路：我们使用两个stack栈来操作，一个保存数据，一个保存最小值（找到相等的和更小的就加进去），值得注意的是，没有元素的时候，无论第一个压进栈的元素是多大，最小值的堆栈都要压进去，出栈的时候如果只剩下一个元素，也是要特殊处理的。

代码如下：

public class MinStack {    public Stackdata=new Stack<>();//保存数据的栈    public Stackmin=new Stack<>();//保存最小值得栈    public MinStack() {        // do initialize if necessary    }    public void push(int number) {//压栈操作        // write your code here        data.push(number);        if(min.size()==0||min.lastElement()>=number){//当该数小于最小值的时候，或者堆栈里面没有数的时候，我们将它压进去。            min.push(number);        }    }    public int pop() {        // write your code here        if(data.size()>0){//数据栈大小不为0            int t=data.lastElement();//得到最小值            if(data.size()==1) {//只剩下一个元素，数据栈要出栈，最小值也是                data.pop();                min.pop();            }else{                data.pop();数据栈出栈                if(min.lastElement()==t){//最小值不一定要出栈                    min.pop();                }            }            return t;        }else//数据栈为空            return 0;    }    public int min() {        // write your code here        if(min.size()>0&&data.size()>0)            return min.lastElement();        else            return 0;    }}

如果有所帮助，脸皮厚求个赞~

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店

更多相关文章

随机推荐