设计一个有 getMin 功能的栈

问题

实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作

要求

  • pop、push、getMin 操作的时间复杂度都是 O(1)
  • 设计的栈类型可以使用现成的栈结构

思路

这个类的设计上,采用两个栈,一个用来保存当前栈中的元素,其功能等同于一个正常的栈,记为 mStack;另一个栈用来保存每一步的最小值,记为 mMinStack.

方案一:

public class MyStack1<T extends Comparable<T>> {

    private Stack<T> mStack;

    private Stack<T> mMinStack;

    public MyStack1() {
        mStack = new Stack<>();
        mMinStack = new Stack<>();
    }


    public void push(T item) {

        if (mMinStack.isEmpty()) {
            mMinStack.push(item);
        } else if (item.compareTo(getMin()) <= 0) {
            mMinStack.push(item);
        }

        mStack.push(item);

    }

    public T pop() {

        if (mMinStack.isEmpty()) {
            throw new RuntimeException("your stack is empty.");
        }

        T item = mStack.pop();

        if (item.compareTo(getMin()) == 0) {
            return mMinStack.pop();
        }

        return item;
    }

    private T getMin() {
        if (mMinStack.isEmpty()) {
            throw new RuntimeException("your stack is empty.");
        }
        return mMinStack.peek();
    }

}

方案二

public class MyStack2<T extends Comparable<T>> {

    private Stack<T> mStack;

    private Stack<T> mMinStack;

    public void push(T item) {

        if (mMinStack.isEmpty()) {
            mMinStack.push(item);
        } else if (item.compareTo(getMin()) <= 0) {
            mMinStack.push(item);
        } else {
            T minItem = mMinStack.peek();
            mMinStack.push(minItem);
        }

        mStack.push(item);

    }

    public T pop() {

        if (mMinStack.isEmpty()) {
            throw new RuntimeException("your stack is empty.");
        }

        mMinStack.pop();

        return mStack.pop();
    }

    private T getMin() {
        if (mMinStack.isEmpty()) {
            throw new RuntimeException("your stack is empty.");
        }
        return mMinStack.peek();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

javascript数组去重方法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

911
来自专栏一枝花算不算浪漫

一道笔试题来理顺Java中的值传递和引用传递

1081
来自专栏吾爱乐享

java之学习用LinkedList模拟栈数据结构的集合并测试

1174
来自专栏文武兼修ing——机器学习与IC设计

左式堆左式堆代码实现

左式堆 性质 零路径长 零路径长的定义为: 零路径长:从节点X到一个没有两个子节点的(有一个子节点或没有子节点)节点的最短距离 对于零路径长,有以下递归的...

31410
来自专栏JavaEdge

"聊胜于无",浅析Java中的原子操作Java的指针Unsafe类i++不是线程安全的1 原子更新基本类型类2 原子更新数组3 AtomicReference(原子更新引用)4 原子更新字段Atomi

6466
来自专栏zhisheng

#每日一题#3

如下代码,执行test()函数后,屏幕打印结果为() public class Test2 { public void add(Byte b) ...

36711
来自专栏菩提树下的杨过

javascript:json数据的页面绑定

web开发中,如果需要将“服务端返回的json对象”绑定到“现有页面上的dom元素”,传统赋值的方式太繁琐,写起来也很累(特别是json对象很大时),于是想出了...

2119
来自专栏机器学习入门

LWC 61:740. Delete and Earn

LWC 61:740. Delete and Earn 传送门:740. Delete and Earn Problem: Given an array nu...

2225
来自专栏Java学习网

Java中处理正则表达式的工具类——总有一个适合你

import java.util.ArrayList; import java.util.List; import java.util.regex.Match...

3215
来自专栏我的技术专栏

数据结构图文解析之:栈的简介及C++模板实现

1575

扫码关注云+社区

领取腾讯云代金券