频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
[算法]求栈中最小元素
2016-05-09 09:18:09         来源:陶程的博客  
收藏   我要投稿

解题思路:

我们经常会采用空间换取时间提高时间复杂度。我们可以使用两个栈结构,一个栈用来存储数据,另一个栈用来存储栈中的最小元素。思路如下:如果当前入栈的元素比原来栈中的最小值还小,则把这个值压入保存最小元素的栈中;在出栈时,如果当前入栈的元素恰好为当前栈中的最小值,保存最小值的栈顶元素也出栈,使得当前最小值变为其入栈之前的那个最小值。

实现代码如下:

package 求栈中最小元素;
/**
 * 用链表方式实现栈
 * @author dream
 *
 * @param 
 */
public class MyStack {

    Node top = null;

    public boolean isEmpty(){
        return top == null;
    }

    public void push(E data){
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
    }

    public E pop(){
        if(isEmpty()){
            return null;
        }
        E data = top.data;
        top = top.next;
        return data;
    }

    public E peek(){
        if(isEmpty()){
            return null;
        }
        return top.data;
    }
}
package 求栈中最小元素;

public class Node {

    Node next = null;
    E data;
    public Node(E data){
        this.data = data;
    }
}
package 求栈中最小元素;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;

public class MyStack1 {

    MyStack elem;
    MyStack min;

    public MyStack1(){
        elem = new MyStack<>();
        min = new MyStack<>();
    }

    public void push(int data){
        elem.push(data);
        if(min.isEmpty()){
            min.push(data);
        }else{
            if(data < min.peek()){
                min.push(data);
            }
        }
    }

    public int pop(){
        int topData = elem.peek();
        elem.pop();
        if(topData == min()){
            min.pop();
        }
        return topData;
    }

    public int min(){
        if(min.isEmpty()){
            return Integer.MAX_VALUE;
        }else {
            return min.peek();
        }
    }

}
点击复制链接 与好友分享!回本站首页
相关TAG标签 算法 元素
上一篇:反射和注解的使用
下一篇:(变长数组)变量也可做特殊数组的长度
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站