当前位置：首页 > 编程日记 > 正文

C++的STL栈实现获取栈中最小元素的成员

编程日记 2024-04-22 08:00:00

实现一个获取栈中最小数据成员的函数，该栈支持如下操作：
1.push(x) : 将元素x压入栈中
2.pop() : 弹出(移除)栈顶元素
3.top() : 返回栈顶元素
4.getMin() : 返回栈内最小元素
要求时间复杂度为O(1)

这里关键是如何获取最小值，栈中的元素不断增加，且要达到O（1）常数级的时间复杂度，即创建好的栈进行排序，返回最小值是不可行的。

这里只有在创建过程中将栈中的最小值获取到，此时一个可行的办法为：
维护一个最小栈，保持栈顶元素为所有元素的最小值，且大小与原本数据栈保持一致。
这样即使有原本数据的删除添加，最小栈同样跟随数据删除添加即可。
在这里插入图片描述
方法一（一个栈）：
数据结构实现如下:

void push(int x) {data_stack.push(x);/*当最小栈中的元素不为空的时候，和栈顶元素进行大小比较，判断是否要入栈*/if (!min_stack.empty()) {if (min_stack.top() > x) {min_stack.push(x);}else {min_stack.push(min_stack.top());}}/*为空的时候即可入栈*/else {min_stack.push(x);}
}
/*此时最小栈的栈顶即为数据栈中的最小元素*/
int get_min(){return min_stack.top();
}

方法二（两个栈）：

class MinStack {stack<int> S;int min=2147483647;
public:/** initialize your data structure here. */MinStack() {}//push操作void push(int x) {if (x <= min) { //当遇到小于等于最小值的数值，将上一个最小值也push到栈中S.push(min);min = x;}S.push(x);}void pop() {if (S.top() == min) { //pop的时候发现pop的时最小值，那么pop两次，同时变更最小值S.pop();min = S.top();S.pop();} else {S.pop();}}int top() {return S.top();}int getMin() {return min;}
};

测试代码实现如下:

#include <stack>
#include <iostream>
#include <algorithm>using namespace std;class My_stack{private:stack<int> data_stack,min_stack;public:void push(int x) {data_stack.push(x);if (!min_stack.empty()) {if (min_stack.top() > x) {min_stack.push(x);}else {min_stack.push(min_stack.top());}}else {min_stack.push(x);}}void pop() {min_stack.pop();data_stack.pop();}int top() {return data_stack.top();}int get_min(){return min_stack.top();}
};int main(){My_stack s;int tmp;cout << "construct the stack " << endl;while(cin >> tmp) {s.push(tmp);}cout << "min is " << s.get_min() << endl;s.pop();cout << "after pop " << s.top() << endl;s.push(-4);cout << "after push ,the top and min is " << s.top() << " " << s.get_min() << endl;return 0;
}

输出如下:

construct the stack 
2 -1 -3 2 0 4
d
min is -3
after pop 0
after push -4,the top and min is -4 -4

https://www.dkcj.cn/info/5050.html

java servlet applet,详解Java Servlet与Applet比较

Java Servlet与Applet相似之处：◆它们不是独立的应用程序，没有main()方法。◆它们不是由用户或程序员调用，而是由另外一个应用程序(容器)调用。◆它们都有一个生存周期，包含init()和destroy()方法。Java Servlet与Applet不同之处&…

编程日记2024/04/22 07:30:00

NTP时间同步服务器搭建

转载：http://blog.s135.com/post/281/ 一、搭建时间同步服务器1、编译安装ntp server tar zxvf ntp-4.2.6.tar.gzcd ntp-4.2.6./configure --prefix/usr/local/ntp --enable-all-clocks --enable-parse-clocksmake && make install注：如以上下载…

编程日记2024/04/22 07:00:00

OI基础系列之最大子数组问题

OI基础系列之最大子数组问题 ——Edward2414 oi退役了，虽然没取得多少成绩，也算是走过一会的人了。我相信绝大多数oi党都是自学成才，在此，我感谢那些把自己所学写到博客里的前辈们，没有你们，我不可能…

编程日记2024/04/22 06:30:00

springCloud Zuul网关

1.springboot 仅2.0.x 支持，在此选择 2.0.7 2.新建Module eureka-zuul-client 3.导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/…

编程日记2024/04/22 06:00:00

f-free 查看系统中空闲和使用的内存

文章目录前言语法格式以指定单位显示内存占用情况打印所有内存占用（RAM SWAP）打印间隔以及次数打印所有的列（将buff和cache分开）free各个空间含义swap交换空间cache页高速缓存free 与 available前言 free 支持查看空闲的和已使用…

编程日记2024/04/22 05:30:00

对比两个同类型的泛型集合并返回差异泛型集合 ——两个List类名的比较

1: /// <summary> 2: /// 对比两个同类型的泛型集合并返回差异泛型集合 3: /// </summary> 4: /// <typeparam name"T">泛型类型</typeparam> 5: /// <param name"newModel">修改后的数据集合</param> 6: /// &…

编程日记2024/04/22 05:00:00

php insert failed,较大的MySQL INSERT语句导致PHP错误

好吧,我正在编写代码,但是发生了一些奇怪的事情,我不认为我的代码是错误的…但是它仍在垂死,我不知道为什么…有错误：Error: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use …

编程日记2024/04/22 04:30:00

js 取得文件大小

document.getElementById("file").files[0].size

编程日记2024/04/22 04:00:00

Spring Boot thymeleaf模版支持，css,js等静态文件添加

Thymeleaf引入 Thymeleaf是一个Java模板引擎开发库，可以处理和生成HTML、XML、JavaScript、CSS和文本，在Web和非Web环境下都可以正常工作。 1.添加依赖包 <dependency><groupId>org.springframework.boot</groupId><artifactId>…

编程日记2024/04/22 03:30:00

s-sed(stream editor) 文本填充和编辑基本使用

文章目录前言语法格式sed 操作地址sed子命令sed正则表达式sed使用实例打印命令 p删除命令 d替换命令 s指定操作地址的范围逗号 ,多重编辑命令 e下行插入命令 a上行插入命令 i修改命令 c获取下一行命令 n转换命令 y退出命令 q总结前言 sed是一个“非交互”式的字符流编辑器&am…

编程日记2024/04/22 03:00:00

c语言动态迁移mysql,flask-migrate动态迁移数据库

了解flask_migrate需要先了解flask-script，那么flask-script的作用是什么呢？flask-script的作用是可以通过命令行的形式来操作Flask。例如通过命令跑一个开发版本的服务器、设置数据库，定时任务等。2.执行pip install flask-script来进行安装…

编程日记2024/04/22 02:30:00

软考之路-网络攻击：主动攻击和被动攻击

被动攻击(针对路上的东西下手) 概念：就是网络窃听，窃取数据包并进行分析，从中窃取重要的敏感信息措施：防止被动攻击的主要手段是数据加密传输主动攻击(针对计算机下手) 概念：包括窃取、篡改、假冒和破坏措施&#x…

编程日记2024/04/22 02:00:00

edge.js架起node.js和.net互操作桥梁

今天要介绍的是edge.js这个github上刚兴起的开源项目，它可以让node.js和.net之间在in-process下互操作。.net版本在4.5及以上，因为.net4.5带来的Task，asyn，await关键字和node.js的Event模型正好匹配。如果你感兴趣的话&#xff0c…

编程日记2024/04/22 01:30:00

connect() failed (111: Connection refused) while connecting to upstream, cli

php-fpm没有运行执行如下命令查看是否启动了php-fpm，如果没有则启动你的php-fpm即可 netstat -ant | grep 9000没有运行为空，有运行显示 tcp 0 0 127.0.0.1:9000 0.0.0.0:* LISTEN 启动方法 sudo /usr/loca…

编程日记2024/04/22 01:00:00

C++的STL 栈实现判断栈的出栈顺序是否合理

有这样的题目： 已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈， 也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法? 类似如下： 已…

编程日记2024/04/22 00:30:00

fire.php,Fire PHP

项目介绍： Fire PHP 是基于 PHP JavaScript开发的跨平台的Firefox 的扩充套件，即PHP调试插件，可以帮你debug 后端PHP 的程式，其使用的技术跟某些IDE 一样，要求你在写程式时加入一些追踪用的代码。通过使用Firephp你可以…

编程日记2024/04/22 00:00:00

json_encode时中文编码转正常状态

function json_encode_cn($data) {$data json_encode($data);return preg_replace("/\\\u([0-9a-f]{4})/ie", "iconv(UCS-2, UTF-8, pack(H*, $1));", $data); }直接json_encode()函数 ["\u6fb3\u5927\u5229\u4e9e","\u8056\u8a95\u5cf6&q…

编程日记2024/04/21 23:30:00

验证URL链接和IP有效性的JS代码（正则表达式）

千里之行，始于足下，因之前毕业设计的耽误，没能在博客园记录我的程序猿体会，稍有遗憾，这么多的时间，我竟让他转瞬而过！但没关系，再次出发，勿忘为什么出发！ 一下…

编程日记2024/04/21 23:00:00

[转帖]什么是光纤的波长？看看有哪些是你不知道的！

什么是光纤的波长？看看有哪些是你不知道的！ FShttps://www.feisu.com/bbs/e-1640.html2017-07-01 00:00:001084我们平时最熟悉的光当然是我们肉眼所能看见的光。我们的眼睛对波长在400nm的紫光到700nm的红光很敏感。但对于携带玻璃纤维的光纤&#xff0…

编程日记2024/04/21 22:30:00

C++的STL 栈实现四则运算

使用栈实现四则运算，支持，-，*，/，(，) 输入为字符串，输出为计算好的数值，如不符合四则运算的规定，则异常退出这个实现借用了栈以及字符处理状态机的思想： 维…

编程日记2024/04/21 22:00:00

javascript小数相减会出现一长串的小数位数的原因

javascript小数相减会出现一长串的小数位数的原因 <script>var a38.8;var b6.8;alert(parseFloat(a)-parseFloat(b));var a134.22;var b6;alert(a*b);</script>以上代码为什么产生一长串小数位出来，虽然比较精确，可没必要呀。这个和数据结构…

编程日记2024/04/21 21:30:00

Java孩子父母类,@Output孩子和父母之间的沟通 . 角2（5）

我正在尝试学习角度2，并且我正在尝试使用来自我的子组件的数据在父组件中设置变量 . 基本上我在父视图中有一个子 Headers ，我希望 Headers 和一些HTML根据加载的子项进行更改 .父组件：import { Component, OnInit, ViewEncapsulation } from…

编程日记2024/04/21 21:00:00

SQL 自学笔记1（W3School）

自学W3Schoolhttp://www.w3school.com.cn/sql/index.asp 简介 SQL是什么？ Structured Query Language 结构化的查询语言 SQL能做什么？ 面向数据库查询、取出数据、插入新数据、更新数据、删除数据在数据库中建立库、表；创建存储过程及视图可设…

编程日记2024/04/21 20:30:00

$sumA[i]=\sum _{j=1}^{i}P[j],sumB[i]=\sum _{j=1}^{i}(L[j]\cdot P[j])$