每日一题——包含min函数的栈
包含min函数的栈
- 题目
- 数据范围：
- 示例
- C语言代码实现
- 解释
- 1. `push(value)`
- 2. `pop()`
- 3. `top()`
- 4. `min()`
- 总结
- 大小堆
- GPT给的原始代码
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value)：将value压入栈中pop()：弹出栈顶元素top()：获取栈顶元素min()：获取栈中最小元素
数据范围：
- 操作数量满足 0 ≤ n ≤ 300 0 \leq n \leq 300 0≤n≤300
- 输入的元素满足 ∣ v a l ∣ ≤ 10000 |val| \leq 10000 ∣val∣≤10000
- 进阶：栈的各个操作的时间复杂度是 O ( 1 ) O(1) O(1)，空间复杂度是 O ( n ) O(n) O(n)
示例
输入：
["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出：
-1, 2, 1, -1
解析：
"PSH-1"表示将-1压入栈中，栈中元素为-1"PSH2"表示将2压入栈中，栈中元素为2, -1"MIN"表示获取此时栈中最小元素==>返回-1"TOP"表示获取栈顶元素==>返回2"POP"表示弹出栈顶元素，弹出2，栈中元素为-1"PSH1"表示将1压入栈中，栈中元素为1, -1"TOP"表示获取栈顶元素==>返回1"MIN"表示获取此时栈中最小元素==>返回-1
C语言代码实现
#define MAX_SIZE 300 // 假设栈最大容量
int stack[MAX_SIZE]; // 定义一个整数数组作为栈的存储空间
int count = -1; // 用于记录栈中元素的数量// 压入栈中的值
void push(int value) {if (count < MAX_SIZE - 1) {stack[++count] = value;} else {printf("Stack is full.\n");return;}
}// 弹出栈顶元素
void pop() {if (count == -1) {printf("Stack is empty.\n");return;}count--;
}// 获取栈顶元素
int top() {if (count == -1) {return -1;}return stack[count]; // 返回栈顶元素的值
}// 获取栈中最小的元素
int min() {if (count == -1) {return -1;}int minVal = stack[0]; for (int i = 1; i <= count; i++) {minVal = (minVal > stack[i]) ? stack[i] : minVal;}return minVal;
}
解释
1. push(value)
该函数负责将一个元素压入栈中。当栈未满时，将元素存入 stack 数组，并将栈顶指针 count 增加。
2. pop()
该函数负责弹出栈顶元素。当栈不为空时，栈顶元素被移除，栈顶指针 count 减少。
3. top()
该函数返回栈顶的元素。如果栈为空，返回 -1，否则返回栈顶的值。
4. min()
该函数遍历整个栈，找到最小的元素并返回。如果栈为空，返回 -1。
总结
这题整体上还是很简单的，本以为是用大小堆实现的，没想到直接一个遍历就搞完了。明天研究一下如何用大小堆实现。
大小堆
GPT给的原始代码
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param value int整型* @return 无*/
#define MAX_SIZE 300 // 假设栈最大容量，定义栈的最大大小为300
int stack[MAX_SIZE]; // 定义一个整数数组作为栈的存储空间
int count = -1; // 用于记录栈中元素的数量，初始化时栈为空
int data[MAX_SIZE]; // 用于存储堆的数据
int size = 0; // 堆中的元素数量，初始化时堆为空/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param 无* @return 无*/
void insertMinHeap(int value) {int i = size++; // 先将堆的大小增加1，并记录当前堆中元素的位置data[i] = value; // 将新元素插入堆的末尾// 将新插入的元素与其父节点比较并进行交换，直到堆的性质得到维护while (i > 0 && data[i] < data[(i - 1) / 2]) { int temp = data[i]; // 交换操作的中间变量data[i] = data[(i - 1) / 2]; // 将父节点值移到当前节点data[(i - 1) / 2] = temp; // 当前节点的值移到父节点i = (i - 1) / 2; // 更新索引，继续与父节点比较}
}// 堆的操作：删除堆顶元素
void removeMinHeap() {if (size == 0) return; // 如果堆为空，直接返回data[0] = data[--size]; // 用堆的最后一个元素替代堆顶元素// 维护堆的性质，逐步下沉替代后的堆顶元素int i = 0; while (2 * i + 1 < size) { // 判断当前节点是否有子节点int left = 2 * i + 1; // 左子节点的索引int right = 2 * i + 2; // 右子节点的索引int smallest = i; // 假设当前节点为最小元素if (left < size && data[left] < data[smallest]) { // 如果左子节点小于当前节点smallest = left; // 更新最小值的索引}if (right < size && data[right] < data[smallest]) { // 如果右子节点小于当前节点smallest = right; // 更新最小值的索引}if (smallest == i) break; // 如果当前节点已经是最小的，结束循环// 交换当前节点与最小子节点int temp = data[i];data[i] = data[smallest];data[smallest] = temp;// 更新索引，继续下沉操作i = smallest;}
}// 堆的操作：获取堆顶元素
void removeValueFromMinHeap(int value) {// 查找堆中要删除的值的索引int index = -1;for (int i = 0; i < size; i++) {if (data[i] == value) {index = i; // 找到对应的索引break;}}// 如果没有找到该值，则返回if (index == -1) {printf("Value %d not found in heap.\n", value);return;}// 用堆的最后一个元素替换要删除的元素data[index] = data[--size];// 从替换位置开始调整堆int i = index;while (2 * i + 1 < size) { // 判断当前节点是否有子节点int left = 2 * i + 1; // 左子节点的索引int right = 2 * i + 2; // 右子节点的索引int smallest = i; // 假设当前节点为最小元素// 找到较小的子节点if (left < size && data[left] < data[smallest]) {smallest = left;}if (right < size && data[right] < data[smallest]) {smallest = right;}// 如果当前节点已经是最小的，就不需要调整了if (smallest == i) break;// 交换当前节点与最小子节点int temp = data[i];data[i] = data[smallest];data[smallest] = temp;// 更新索引，继续调整下去i = smallest;}
}// 从栈中弹出一个元素
void pop() {if (count == -1) { // 如果栈为空，打印提示信息并返回printf("Stack is empty.\n");return;}int value = stack[count--]; // 取出栈顶元素并更新栈的计数器// 删除堆中的该值removeValueFromMinHeap(value);
}// 返回栈顶元素
int top() {return stack[count]; // 返回栈顶元素的值
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param 无* @return int整型*/
int min() {// 返回堆顶元素，也就是最小值return size > 0 ? data[0] : -1; // 如果堆不为空，返回堆顶元素；否则返回-1
}// 向栈中推入一个新元素
void push(int value) {if (count < MAX_SIZE - 1) { // 判断栈是否已满stack[++count] = value; // 将元素推入栈insertMinHeap(value); // 将元素插入最小堆} else {printf("Stack is full.\n"); // 如果栈满了，打印提示信息}
}通过结合栈和最小堆的操作，我们能够实现一个高效的栈结构，在常见的栈操作上（如压栈、弹栈）同时保证能够快速查询栈中的最小元素。一个栈用来存储数据，一个大小堆用来排序
最难的还是栈里面删除，大小堆已经排序过后必须找到特定的删除。挺难解决的。
相关文章：
每日一题——包含min函数的栈
包含min函数的栈 题目数据范围：示例C语言代码实现解释1. push(value)2. pop()3. top()4. min() 总结大小堆GPT给的原始代码 题目 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 mi…...
【最后203篇系列】004 -Smarklink
说明 这个用来替代nginx。 最初是希望用nginx进行故障检测和负载均衡，花了很多时间，大致的结论是：nginx可以实现，但是是在商业版里。非得要找替代肯定可以搞出来，但是太麻烦了（即使是nginx本身的配置也很烦…...
二分法模板
数组具有二段性，可以分为左右两边合法区和不合法区 如果选择左端点，右边区域不合法，选择 left mid ,right mid - 1; 如果选择右端点，左边区域不合法，选择 left mid 1 ,right mid ; 1.x 的平方根 LCR 072. x 的…...
)
基于SpringBoot的智慧康老疗养院管理系统的设计与实现(源码+SQL脚本+LW+部署讲解等)
专注于大学生项目实战开发,讲解,毕业答疑辅导，欢迎高校老师/同行前辈交流合作✌。 技术范围：SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容：…...
LabVIEW无人机航线控制系统
介绍了一种无人机航线控制系统，该系统利用LabVIEW软件与MPU6050九轴传感器相结合，实现无人机飞行高度、速度、俯仰角和滚动角的实时监控。系统通过虚拟仪器技术，有效实现了数据的采集、处理及回放，极大提高了无人机航线的控制精度…...
STM32CUBEIDE编译的hex使用flymcu下载后不能运行
测试后确认，不论是1.10版本还是1.16版本，编译生成的hex下载后不能运行，需要更改boot 设置才能开始运行，flymcu下载后已经告知一切正常，跳转到8000 0000处开始运行，实际没有反应，而使用mdk编译生…...
final-关键字
一、final修饰的类不能被继承 当final修饰一个类时，表明这个类不能被其他类继承。例如，在 Java 中，String类就是被final修饰的，这保证了String类的不可变性和安全性，防止其他类通过继承来改变String类的行为。 final…...
在RHEL 8.10上安装开源工业物联网解决方案Thingsboard 3.9
在RHEL/CentOS/Rocky/AlmaLinux/Oracle Linux 8单节点上安装 备注： 适用于单节点 是否支持欧拉？？？ 前提条件 本指南描述了如何在RHEL/CentOS 7/8上安装ThingsBoard。硬件要求取决于所选的数据库和连接到系统的设备数量。要在单…...
deepseek+vscode自动化测试脚本生成
近几日Deepseek大火，我这里也尝试了一下，确实很强。而目前vscode的AI toolkit插件也已经集成了deepseek R1，这里就介绍下在vscode中利用deepseek帮助我们完成自动化测试脚本的实践分享 安装AI ToolKit并启用Deepseek 微软官方提供了一个针对AI辅助的插件，也就是 AI Toolk…...
k8s支持自定义field-selector spec.hostNetwork过滤
好久没写博客啦，年前写一个博客就算混过去啦😂 写一个小功能，对于 Pod，在没有 label 的情况下，支持 --field-selector spec.hostNetwork 查询 Pod 是否为 hostNetwork 类型，只为了熟悉 APIServer 是如何构…...
图像噪声处理技术：让图像更清晰的艺术
在这个数字化时代，图像作为信息传递的重要载体，其质量直接影响着我们的视觉体验和信息解读。然而，在图像采集、传输或处理过程中，难免会遇到各种噪声干扰，如高斯噪声、椒盐噪声等，这些噪声会降低图像的清晰…...
w186格障碍诊断系统spring boot设计与实现
🙊作者简介：多年一线开发工作经验，原创团队，分享技术代码帮助学生学习，独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取，记得注明来意哦~🌹赠送计算机毕业设计600个选题excel文…...
【自学笔记】Java的重点知识点-持续更新
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 Java知识点概览一、Java简介二、Java基本语法三、面向对象编程（OOP）四、异常处理五、常用类库六、多线程编程七、网络编程 注意事项 总结 Ja…...
031.关于后续更新和指纹浏览器成品
关于后续更新 后续决定不再更新了，我低估了各种检测站的更新速度，我开源的一些源码修改方法，已经被个别检测网站加入了针对性检测。只要开源了，一段时间后就会有针对性反检测。这种东西根本就不能开源，开源了大家就一…...
013-51单片机红外遥控器模拟控制空调，自动制冷制热定时开关
主要功能是通过红外遥控器模拟控制空调，可以实现根据环境温度制冷和制热，能够通过遥控器设定温度，可以定时开关空调。 1.硬件介绍 硬件是我自己设计的一个通用的51单片机开发平台，可以根据需要自行焊接模块，这是用立创…...
UE5 蓝图学习计划 - Day 10：UI 系统（HUD 与 Widget）
在游戏开发中，UI（用户界面） 是玩家获取游戏信息、与游戏进行交互的重要部分。Unreal Engine 5 提供了 HUD（Head-Up Display） 和 Widget Blueprint（小部件蓝图） 来帮助开发者创建 血量条、得分系…...
QT简单实现验证码(字符）
0） 运行结果 1） 生成随机字符串 Qt主要通过QRandomGenerator类来生成随机数。在此之前的版本中，qrand()函数也常被使用，但从Qt 5.10起，推荐使用更现代化的QRandomGenerator类。 在头文件添加void generateRandomNumb…...
代码随想录刷题笔记
数组 二分查找 ● 704.二分查找 tips：两种方法，左闭右开和左闭右闭，要注意区间不变性，在判断mid的值时要看mid当前是否使用过 ● 35.搜索插入位置 ● 34.在排序数组中查找元素的第一个和最后一个位置 tips：寻找左右边…...
VSCode 中的 Git Graph扩展使用详解
VSCode 中的 Git Graph 详解 1. 什么是 Git Graph？ Git Graph 是 VSCode 中的一款 Git 可视化扩展，它提供了一种 图形化方式 来查看 Git 提交历史、分支、合并记录等信息，使得 Git 版本管理更加直观和高效。 通过 Git Graph，你…...
Day07：缓存-数据淘汰策略
Redis的数据淘汰策略有哪些 ? （key过期导致的） 在redis中提供了两种数据过期删除策略 第一种是惰性删除，在设置该key过期时间后，我们不去管它，当需要该key时，我们再检查其是否过期，如果过期&…...
【自学嵌入式（8）天气时钟：天气模块开发、主函数编写】
天气时钟：天气模块开发、主函数编写 I2C协议和SPI协议I2C（Inter-Integrated Circuit）SPI（Serial Peripheral Interface） 天气模块心知天气预报使用HTTPClient类介绍主要功能常用函数注意事项 JSON介绍deserializeJson函…...
简单的SQL语句的快速复习
语法的执行顺序 select 4 字段列表 from 1 表名列表 where 2 条件列表 group by 3 分组前过滤 having 分组后过滤 order by 5 排序字段列表 limit 6 分页参数 聚合函数 count 统计数量 max 最大值 min 最小值 avg 平均 sum 总和 分组查询使…...
跟李沐学AI：视频生成类论文精读（Movie Gen、HunyuanVideo）
Movie Gen：A Cast of Media Foundation Models 简介 Movie Gen是Meta公司提出的一系列内容生成模型，包含了 3.2.1 预训练数据 Movie Gen采用大约 100M 的视频-文本对和 1B 的图片-文本对进行预训练。 图片-文本对的预训练流程与Meta提出的 Emu: Enh…...
Rust 所有权特性详解
Rust 所有权特性详解 Rust 的所有权系统是其内存安全的核心机制之一。通过所有权规则，Rust 在编译时避免了常见的内存错误（如空指针、数据竞争等）。本文将从堆内存与栈内存、所有权规则、变量作用域、String 类型、内存分配、所有权移动、Cl…...
基于人脸识别的课堂考勤系统
该项目是一个基于人脸识别的课堂考勤系统，使用Python开发，结合了多种技术实现考勤功能。要开发类似的基于人脸识别的考勤系统，可参考以下步骤： 环境搭建：利用Anaconda创建虚拟环境，指定Python版本为3.8&am…...
Deepseek R1 本地化部署指南：跨平台实战
引言 Deepseek R1 作为一款强大的本地化人工智能工具，支持在多种操作系统上部署，满足开发者和企业私有化运行的需求。本文将手把手教你如何在 Windows、Linux 和 macOS 系统上完成 Deepseek R1 的本地化部署，并附赠常见问题解决技巧！ © ivwdcwso (ID: u012172506) 1…...
Nginx 运维开发高频面试题详解
一、基础核心问题 原文链接：https://blog.csdn.net/weixin_51146329/article/details/142963853 1、什么是Nginx？ Nginx 是一个高性能的 HTTP 和反向代理服务器，它以轻量级和高并发处理能力而闻名。Nginx 的反向代理功能允许它作为前端服务…...
JVM运行时数据区域-附面试题
Java虚拟机在执行Java程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域 有各自的用途，以及创建和销毁的时间，有的区域随着虚拟机进程的启动而一直存在，有些区域则是 依赖用户线程的启动和结束而建立和销毁。 1. 程序计…...
DeepSeek本地部署详细指南
DeepSeek本地部署详细指南 随着人工智能技术的飞速发展，本地部署大模型的需求也日益增加。DeepSeek作为一款开源且性能强大的大语言模型，提供了灵活的本地部署方案，让用户能够在本地环境中高效运行模型，同时保护数据隐私。以下是…...
Debian 10 中 Linux 4.19 内核在 x86_64 架构上对中断嵌套的支持情况
一、中断嵌套的定义与原理 中断嵌套是指在一个中断处理程序（ISR）正在执行的过程中，另一个更高优先级的中断请求到来，系统暂停当前中断处理程序，转而处理新的高优先级中断。处理完高优先级中断后，系统返回到原来的中断处理程序继续执行。这种机制允许系统更高效地响应紧急…...
C语言：深入了解指针1
内存和地址 1. 酒店房间类比内存和地址 场景描述 把计算机的内存想象成一家酒店，每个房间就是一个内存单元，每个房间都有一个唯一的房间号，这个房间号就相当于内存地址。房间里可以存放客人的行李等物品，这些物品就好比存储在内…...
【AI】探索自然语言处理（NLP）：从基础到前沿技术及代码实践
Hi ！ 云边有个稻草人-CSDN博客 必须有为成功付出代价的决心，然后想办法付出这个代价。 目录 引言 1. 什么是自然语言处理（NLP）？ 2. NLP的基础技术 2.1 词袋模型（Bag-of-Words，BoWÿ…...
游戏引擎 Unity - Unity 下载与安装
Unity Unity 首次发布于 2005 年，属于 Unity Technologies Unity 使用的开发技术有：C# Unity 的适用平台：PC、主机、移动设备、VR / AR、Web 等 Unity 的适用领域：开发中等画质中小型项目 Unity 适合初学者或需要快速上手的开…...
文本复制兼容方案最佳实现落地。
文章目录 一、navigator.clipboard.writeText二、方案落地总结 一、navigator.clipboard.writeText navigator.clipboard.writeText 是一个Web API，它允许网页脚本将文本数据写入用户的系统剪贴板。这个API是异步的，并且设计用于提高安全性和用户体验&a…...
LabVIEW如何高频采集温度数据?
在LabVIEW中进行高频温度数据采集时，选择合适的传感器（如热电偶或热电阻）和采集硬件是关键。下面是一些建议，帮助实现高效的温度数据采集： 1. 传感器选择： 热电偶（Thermocouple）&am…...
AI智慧社区--人脸识别
前端 人脸的采集按钮： 首先对于选中未认证的居民记录，进行人脸采集 前端的按钮 <el-form-item><el-button v-has"sys:person:info" type"info" icon"el-icon-camera" :disabled"ids.length < 0" …...
C++11—右值引用
目录 简介 左值和右值 左值 右值 右值引用 生命周期 引用折叠 实际应用 移动语义 移动构造函数 移动赋值运算符 完美转发 简介 之前我们曾学习过引用叫左值引用，但那是C98的，在C11中新增了一种引用叫右值引用。右值引用主要用于支持移动语…...
Workbench 中的热源仿真
探索使用自定义工具对移动热源进行建模及其在不同行业中的应用。 了解热源动力学 对移动热源进行建模为各种工业过程和应用提供了有价值的见解。激光加热和材料加工使用许多激光束来加热、焊接或切割材料。尽管在某些情况下，热源 （q） 不是通…...
Windows11 不依赖docker搭建 deepseek-R1 1.5B版本（附 Open WebUi搭建方式）
零、前言 过年这几天发现 DeepSeek 非常火，试用了一下发现确实不错。与豆包、kimi、perplexity 这些相比完全不是一个次元的存在，特别是用ta写文章的时候体验非常好。所以试着自己搭一个环境。 一、安装 Ollama和DeepSeek-R1 我的安装方式很简单…...
Error: Expected a mutable image
你的函数用了不支持的图片格式比如我的人脸检测，本来要RGB565我却用JPEG所以报错...
【4Day创客实践入门教程】Day2 探秘微控制器——单片机与MicroPython初步
Day2 探秘微控制器——单片机与MicroPython初步 目录 Day2 探秘微控制器——单片机与MicroPython初步MicroPython语言基础开始基础语法注释与输出变量模块与函数 单片机基础后记 Day0 创想启程——课程与项目预览Day1 工具箱构建——开发环境的构建Day2 探秘微控制器——单片机…...
代码随想录算法训练营Day51 | 101.孤岛的总面积、102.沉没孤岛、103.水流问题、104.建造最大岛屿
文章目录 101.孤岛的总面积思路与重点 102.沉没孤岛思路与重点 103.水流问题思路与重点 104.建造最大岛屿思路与重点 101.孤岛的总面积 题目链接：101.孤岛的总面积讲解链接：代码随想录状态：直接看题解了。 思路与重点 nextx或者nexty越界了…...
网络基础
协议 协议就是约定 网络协议是协议中的一种 协议分层 协议本身也是软件，在设计上为了更好的模块化，解耦合，也是设计成为层状结构的 两个视角： 小白：同层协议，直接通信 工程师：同层协议&…...
利用Spring Batch简化企业级批处理应用开发
1. 引言 1.1 批处理的重要性 在现代企业系统中，批处理任务用于处理大量数据，如报表生成、数据迁移、日终结算等。这些任务通常不需要实时响应，但需要高效、可靠地完成。批处理可以显著提高系统性能，减少实时系统的负载，并确保数据的完整性和一致性。 1.2 Spring Batch简…...
Python - pyautogui库 模拟鼠标和键盘执行GUI任务
安装库： pip install pyautogui 导入库：import pyautogui 获取屏幕尺寸： s_width, s_height pyautogui.size() 获取鼠标当前位置： x, y pyautogui.position() 移动鼠标到指定位置（可以先使用用上一个函数调试获取当…...
UE求职Demo开发日志#19 给物品找图标，实现装备增加属性，背包栏UI显示装备
1 将用到的图标找好，放一起 DataTable里对应好图标 测试一下能正确获取： 2 装备增强属性思路 给FMyItemInfo添加一个枚举变量记录类型（物品，道具，装备，饰品，武器）--> 扩展DataT…...
【PyQt】lambda函数，实现动态传递参数
为什么需要 lambda？ 在 PyQt5 中，clicked 信号默认会传递一个布尔值（表示按钮是否被选中）。如果我们希望将按钮的文本内容传递给槽函数，需要通过 lambda 函数显式传递参数。 这样可以实现将按钮内容传递给槽函数&…...
Unity 2D实战小游戏开发跳跳鸟 - 跳跳鸟碰撞障碍物逻辑
在有了之前创建的可移动障碍物之后，就可以开始进行跳跳鸟碰撞到障碍物后死亡的逻辑，死亡后会产生一个对应的效果。 跳跳鸟碰撞逻辑 创建Obstacle Tag 首先跳跳鸟在碰撞到障碍物时，我们需要判定碰撞到的是障碍物，可以给障碍物的Prefab预制体添加一个Tag为Obstacle，添加步…...
LeetCode：121.买卖股票的最佳时机1
跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！ 代码随想录 LeetCode：121.买卖股票的最佳时机1 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票…...
DeepSeek-R1 论文. Reinforcement Learning 通过强化学习激励大型语言模型的推理能力
论文链接： [2501.12948] DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning 实在太长，自行扔到 Model 里，去翻译去提问吧。 工作原理： 主要技术，就是训练出一些专有用途小模型&…...