定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。

2023-11-08

/**
 * 定义栈的数据结构,请在该类型中实现一个能够得到校的最小元素的min函数。
 * 在该栈中,调用pop、push 及min的时间复杂度都是0(1)
 * @param <T> 泛型参数
 */
public static class StackWithMin<T extends Comparable<T>> {
        // 数据栈,用于存放插入的数据
        private Stack<T> dataStack;
        // 最小数位置栈,存放数据栈中最小的数的位置
        private Stack<Integer> minStack;

        // 构造函数
        public StackWithMin() {
            this.dataStack = new Stack<>();
            this.minStack = new Stack<>();
        }

        /**
         * 出栈方法
         * @return 栈顶元素
         */
        public T pop() {
            // 如果栈已经为空,再出栈抛出异常
            if (dataStack.isEmpty()) {
                throw new RuntimeException("The stack is already empty");
            }

            // 如果有数据,最小数位置栈和数据栈必定是有相同的元素个数,
            // 两个栈同时出栈
            minStack.pop();
            return dataStack.pop();
        }

        /**
         * 元素入栈
         * @param t 入栈的元素
         */
        public void push(T t) {
            // 如果入栈的元素为空就抛出异常
            if (t == null) {
                throw new RuntimeException("Element can be null");
            }

            // 如果数据栈是空的,只接将元素入栈,同时更新最小数栈中的数据
            if (dataStack.isEmpty()) {
                dataStack.push(t);
                minStack.push(0);
            }
            // 如果数据栈中有数据
            else {
                // 获取数据栈中的最小元素(未插入t之前的)
                T e = dataStack.get(minStack.peek());
                // 将t入栈
                dataStack.push(t);
                // 如果插入的数据比栈中的最小元素小
                if (t.compareTo(e) < 0) {
                    // 将新的最小元素的位置入最小栈
                    minStack.push(dataStack.size() - 1);
                } else {
                    // 插入的元素不比原来的最小元素小,复制最小栈栈顶元素,将其入栈
                    minStack.push(minStack.peek());
                }
            }
        }

        /**
         * 获取栈中的最小元素
         * @return 栈中的最小元素
         */
        public T min() {
            // 如果最小数公位置栈已经为空(数据栈中已经没有数据了),则抛出异常
            if (minStack.isEmpty()) {
                throw new RuntimeException("No element in stack.");
            }

            // 获取数据栈中的最小元素,并且返回结果
            return dataStack.get(minStack.peek());
        }
    }

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。 的相关文章

  • 剑指 Offer 39. 数组中出现次数超过一半的数字(java+python)

    数组中有一个数字出现的次数超过数组长度的一半 请找出这个数字 你可以假设数组是非空的 并且给定的数组总是存在多数元素 示例 1 输入 1 2 3 2 2 2 5 4 2 输出 2 限制 1 lt 数组长度 lt 50000 java cla
  • 39_MoreThanHalfNumber 数组中超过一半的元素

    数组中有一个数字出现的次数超过数组长度的一半 请找出这个数字 你可以假设数组是非空的 并且给定的数组总是存在多数元素 示例 1 输入 1 2 3 2 2 2 5 4 2 输出 2 1 利用hashmap统计数组中元素出现的次数 如果次数大于
  • 剑指Offer 04. 二维数组中的查找

    原题链接 思路 题目中说 每一行都是 从左向右递增的 在一个递增的序列中 查找某个数是否是存在的 二分即可 注意对边界进行判断 时间复杂度 O nlogn 代码 class Solution public boolean check int
  • 树14--二叉搜索树的第k个结点

    树14 二叉搜索树的第k个结点 jz62 题目概述 解析 参考答案 注意事项 说明 题目概述 算法说明 给定一棵二叉搜索树 请找出其中的第k小的TreeNode结点 测试用例 输入 5 3 7 2 4 6 8 3 返回值 4 说明 按节点数
  • 面试题 31:连续子数组的最大和(滴滴的“连续最大和”)

    刚才在笔滴滴的测试开发 编程题第一个就是求连续子数组的最大和问题 这个题在 剑指offer 也有这么一道题 题目描述如下 输入一个整型数组 数组里有正数也有负数 数组中一个或连续多个的多个整数组成一个子数组 求所有子数组的和的最大值 要求时
  • LeetCode-二进制中1的个数

    计算机中的补数是 两个数加起来等于在二进制里一个非常整的数 比如 加起来等于 10000000000000000000000000000000000这样的 1 01 的补数 111111111111111111111111111111111
  • 剑指offer_第20题_包含min函数的栈_Python

    题目描述 定义栈的数据结构 并在该类型中实现一个能够得到栈中所含最小元素的min函数 时间复杂度应为O 1 理解 什么是栈 算法复杂度 解题思路 思路1 class Solution def init self self stack sel
  • 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。

    定义栈的数据结构 请在该类型中实现一个能够得到校的最小元素的min函数 在该栈中 调用pop push 及min的时间复杂度都是0 1 param
  • LeetCode-重建二叉树

    先利用前序遍历找根节点 前序遍历的第一个数 就是根节点的值 在中序遍历中找到根节点的位置 k 则 k 左边是左子树的中序遍历 右边是右子树的中序遍历 假设左子树的中序遍历的长度是 l 则在前序遍历中 根节点后面的 l 个数 是左子树的前序遍
  • 剑指 Offer 66. 构建乘积数组(java+python)

    给定一个数组 A 0 1 n 1 请构建一个数组 B 0 1 n 1 其中 B i 的值是数组 A 中除了下标 i 以外的元素的积 即 B i A 0 A 1 A i 1 A i 1 A n 1 不能使用除法 示例 输入 1 2 3 4 5
  • 剑指offer_第17题_树的子结构_Python

    题目描述 输入两棵二叉树A B 判断B是不是A的子结构 其中空树不是任意一个树的子结构 class TreeNode def init self x self val x self left None self right None 解题思
  • LeetCode-替换空格

    创建一个新的string 一边遍历原字符串的每一个字符 一边往新的字符串中写入 遇到空格替换为 20即可 class Solution public string replaceSpaces string str string res fo
  • JZ15 二进制中1的个数

    输入一个整数 n 输出该数32位二进制表示中1的个数 其中负数用补码表示 数据范围 2 31 lt n lt 2 31 1 231 lt n lt 231 1 即范围为 2147483648 lt n lt 2147483647 21474
  • 【剑指Offer】(字符串)左旋转字符串(翻转操作)

    题目链接 https www nowcoder com practice 12d959b108cb42b1ab72cef4d36af5ec tpId 13 tqId 11196 tPage 1 rp 1 ru ta coding inter
  • Acwing-二叉树的镜像

    遍历树中的所有点 每次遍历完之后把左右儿子swap一下 Definition for a binary tree node struct TreeNode int val TreeNode left TreeNode right TreeN
  • Acwing-包含min函数的栈

    stk表示存入这些数据的栈 stk min表示栈里面前i数中的最小值是多少 class MinStack public stack
  • 剑指 Offer 29. 顺时针打印矩阵(java+python)

    输入一个矩阵 按照从外向里以顺时针的顺序依次打印出每一个数字 示例 1 输入 matrix 1 2 3 4 5 6 7 8 9 输出 1 2 3 6 9 8 7 4 5 示例 2 输入 matrix 1 2 3 4 5 6 7 8 9 10
  • 剑指 Offer 25. 合并两个排序的链表(java+python)

    输入两个递增排序的链表 合并这两个链表并使新链表中的节点仍然是递增排序的 示例1 输入 1 gt 2 gt 4 1 gt 3 gt 4 输出 1 gt 1 gt 2 gt 3 gt 4 gt 4 限制 0 lt 链表长度 lt 1000 思
  • 12、剪绳子——剑指offer——动态规划

    剪绳子 问题描述 给你一根长度为n的绳子 请把绳子剪成m段 m和n都是整数 n gt 1并且m gt 1 每段绳子的长度记为k 0 k 1 k m 请问k 0 k 1 k m 可能的最大乘积是多少 首先本题可以用贪婪算法和动态规划算法求解
  • 剑指 Offer 05. 替换空格(java+python)

    请实现一个函数 把字符串 s 中的每个空格替换成 20 示例 1 输入 s We are happy 输出 We 20are 20happy 限制 0 lt s 的长度 lt 10000 java StringBuilder StringB

随机推荐

  • C++使用当multiset插入相同的数时 新插入的数在已有数的左边还是右边呢

    答案 在multiset中 元素按照特定的顺序进行排序并存储 当向multiset插入相同的数时 新插入的数将被放置在已有数的右边 multiset允许存储重复的元素 并且保持了元素的顺序 因此 如果已经存在相同的数 新插入的数将被放置在它
  • c++在线编辑器

    c 在线编辑器 Compiler Explorer Coliru Ideone 乱糟糟的不推荐 C Shell CodingGround 可用来美化代码 慢的很 Judge0 IDE Compiler Explorer https godb
  • P1088 [NOIP2004 普及组] 火星人(全排列)

    题目链接 火星人 思路分析 分析题目题意得到 这个题目关于全排列的问题 题目输入N M分别代表对1 N进行全排列 火星人给出的大数就是1 N全排列的一种情况 对全排列的所有情况进行编号 例如下图 例如上图N 3 假设M 2 给出一种全排列序
  • ffmpeg推流收流 1920*1080视频 花屏

    自己用ffmpeg推流 然后再收流 小分辨率没有问题 当分辨率为1920 1080时 出现花屏现象 尤其是码率高时 现象更加明显 尝试各种办法 最后用下面的办法解决 在ffmpeg源码udp c中 define UDP MAX PKT SI
  • Ubuntu22.04配置静态IP-网关-DNS

    要在Ubuntu系统中配置网络 可以通过以下步骤进行操作 1 打开终端 可以使用 Ctrl Alt T 快捷键打开终端 或者从应用程序菜单中找到 终端 2 检查网络接口 输入以下命令检查当前系统中的网络接口列表 ifconfig a 接口列
  • 贝叶斯网络python实战(以泰坦尼克号数据集为例,pgmpy库)

    文章目录 贝叶斯网络简介 贝叶斯推断思路 贝叶斯网络 贝叶斯网络的实现 应用步骤 泰坦尼克数据集背景介绍 模型结构搭建 模型参数构建 贝叶斯估计器 推理 自动设计网络结构 gt 使用结构学习方法 模型保存 先验 练手数据集 Binary C
  • 三大排序算法

    目录 大O和推导过程 冒泡排序 冒泡排序的思路 冒泡排序的实现 冒泡排序的效率 O N 选择排序 选择排序的思路 选择排序实现 选择排序的效率 O N 插入排序 插入排序的思路 插入排序的实现 插入排序的效率 O N 大O和推导过程 公司规
  • 2023美赛C题:预测Wordle结果-思路详解及参考代码

    一 题目解析 总体来看与去年的C题比较相似 唯一一道有数据 不需要自己额外找 的题目 选题人估计也最多 本质是数据分析题目 需要建立预测模型 分类模型 特征挖掘等 相对来说出思路比较简单 想出彩比较难 所以在分析建模时一定要多维度思考 不然
  • spring三级缓存解决循环依赖

    一 循环依赖 简单说就是 A类中有B属性 B类中有A属性 创建A对象时发现有B属性 就开始创建B对象 此时时又发现B对象中有A属性 又要创建A对象 产生循环依赖现象 示例图 二 Spring解决循环依赖 使用缓存解决循环依赖的流程图 spr
  • 计算机高级应用大赛,理工学院成功开展第三届计算机应用技能竞赛之高级OFFCIE应用大赛...

    为提升学生计算机办公软件应用技能 进一步激发学生的学习兴趣 11月21日下午 理工学院第三届计算机应用技能竞赛之高级OFFCIE应用大赛在A5401 A5403 A5411三个机房成功举行 323名学生报名参加此次竞赛 竞赛分为Word E
  • 嵌入式Linux(五)—嵌入式C语言(运算符2)

    目录 逻辑结构 类型修饰符 auto register 补充 内存和寄存器的关系 Static 静态 Extern 外部申明 Const Volatile 运算符 算数运算操作 逻辑运算 或 与 位运算 移位 赋值运算 内存访问 逻辑结构
  • Windows 网络编程

    Winsock是Windows下网络编程的规范 该规范是Windows下得到广泛应用的 开放的 支持多种协议的网络编程接口 在MFC中MS为套接口 提供了相应的类CAsyncSocket和CSocket CAsyncSocket提供基于异步
  • securecrt破解版64位

    securecrt 破解版是一款支持SSH1和SSH2的终端仿真程序 这个程序能够在windows系统中登陆UNIX或Linux的服务器主机并且还能进行管理设置 是一款非常强大的ssh传输软件 是用于连接运行包括Windows UNIX和V
  • 激发新动能 多地发力数字经济

    发力数字经济 地方正紧锣密鼓展开新一轮规划部署 近期 云南 陕西 江苏 江西等多地出台相关举措 明确未来几年数字经济核心产业发展目标 并进一步完善资金 人才等配套政策 相关专家表示 发展数字经济是把握新一轮科技革命和产业变革新机遇的战略选择
  • 学习日记——时钟温湿计_Demo

    程序例程 如果成功接入则进入SNTP初始化 如果连接时候wifi错误或者是密码错误进入微信智能配网 以上步骤和微信智能配网相同 增加了SNTP初始化这一步 配网成功也执行SNTP初始化 SNTP初始化执行完毕之后每隔一秒种获取网络时间 并且
  • 【解决】控制台解析preview和response数据不一致,并使用transformResponse修改响应数据

    问题 控制台解析preview和response数据不一致 比如 id 1246000001606460673 会被默认解析成 id 1246000001606460700 在Preview 预览功能 中 控制台会把发送过来的json数据自
  • C++ 性能优化篇四《优化字符串的使用:案例研究》

    只有少数人才能触摸到魔法琴弦 string 可是聒噪的名声却企图击败他们 悲哀于那些从来都不歌唱的人们 死亡时却要带着他们的音乐陪葬 奥利弗 温德尔 霍姆斯 1 无声 1858 C 的 std string 类模板是 C 标 准 库 中 使
  • 转贴:华为 SmartAX MT800 固件升级(升级为VC100R004C01B010)并开启路由全过程(2004年8月7日更新) [精华]

    http bbs pcshow net cgi bin threaded show cgi tid 350483777 h 1 bpg 1 age 1 请认真的看上面的文章 如果软件版本低的话 要升级 1为升级工具 2为升级的软件包 升级之
  • 正式发布!中国首个LF Edge捐赠项目Baetyl 2.2发布

    Baetyl作为中国首个加入LFEdge基金会的边缘计算项目 自2019年由百度捐赠以来 在开放中立的社区环境中得到不断的支持与发展 在众多活跃的贡献者的努力下 Baetyl实现了更多具有挑战性的功能 正式升级为Baetyl v2 2版本
  • 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。

    定义栈的数据结构 请在该类型中实现一个能够得到校的最小元素的min函数 在该栈中 调用pop push 及min的时间复杂度都是0 1 param