PTA 栈 (20分)(全网首发)(实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1))_来老铁干了这碗代码的博客-程序员宅基地

技术标签: 数据结构  

题目描述:

我们知道平凡的栈有几个操作:

push(value) 将 value 压入栈 pop() 将栈顶元素弹出, 并返回这个弹出的元素。

现在我们想要在平凡栈的基础上实现以下几个操作:

push(val) 将 val 压入栈;
pop() 将栈顶元素弹出;
min() 返回栈中元素的最小值。

输入格式:

第一行输入一个N( 0=<N<=1000000),代表有N行操作。 接下来N行每行有一个操作,题目保证操作不会越界.

输出格式:

输出每次查询min()时的结果,pop()不用输出

输入样例:

6
push 1
min
push 2
min
push 3
min

输出样例:

1
1
1

分析:

全网首发啊有木有-_-||,这道PTA题其实是一道经典面试题的改编版,本题要求输入小于100W种操作,时间限制在600ms,这就要求我们只能用O(n)或O(nlogn)去实现,毋庸置疑遍历n种操作的循环必须有,所以就要求最小值时的复杂度为o(1),由此引出一个经典思想:空间换时间。下面给出代码:

代码:

#include<iostream>
#include<stdio.h>
int a[1000005], b[1000005];				//a是存放所有值的,b是存放小值的 ,从1开始存放 
int main() {
    
	int num1 = 0, num2 = 0;					//a、b数组的计数器 ,0代表无存放 
	int n;
	scanf("%d", &n);
	while(n--) {
    
		char s[5];
		scanf("%s", &s);
		if(s[1] == 'u') {
    
			int x;
			scanf("%d", &x);
			if(!num1) {
    
				a[++num1] = x; b[++num2] = x;
 			} else {
    
 				a[++num1] = x;
 				if(x <= b[num2]) b[++num2] = x;
			}
		} else if(s[1] == 'o') {
    
			if(a[num1] == b[num2]) {
     a[num1--] = 0;  b[num2--] = 0; }
			else a[num1--] = 0;
		} else printf("%d\n", b[num2]);
	} 
return 0; } 


二更:
有评论反应代码无法运行, 已做调整。 无法运行的原因是:
代码中a,b数组的规模都开到了100w, 而规模50w以上的数组就要定义为全局变量, 否则会报错。

收获:

1、空间换时间的思想
2、C语言比C++要高效一些


每日分享:

平时在做题的时候,一定要寻找最优解,而不是 ac 了就不管了,应该多看看别人的解法。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43899069/article/details/104408738

智能推荐

matlab误差棒的是,[MATLAB图像处理] 有个关于双误差棒的问题_住颜的博客-程序员宅基地

有个关于双误差棒的问题 程序如下 那位大侠解释下我究竟那里出错了啊 运行了不出结果function errorbarxy(x,y,lx,ly,ux,uy,linecol,errorcol,lw,ms,mf)if exist('linecol','var')==0 | isempty(linecol)linecol='b';endif exist('errorcol','var')==0 |...

oracle,如何查看视图结构,获得视图中的字段名称、字段类型、字段长度等。..._weixin_30776863的博客-程序员宅基地

需要获得一个视图中的字段名称、字段类型、字段长度等信息,该如何编写sql语句。通过select*fromuser_views可以获得给定用户下所有的视图名称了,但是没找到如何获取视图结构的解决方法,求路过的大神解惑。已经解决了。all_tab_cols/all_tab_columns查看所有用户下的表及视图结构user_tab_cols/user_tab_colum...

Leaflet使用vector tiles样式设置_weixin_30553065的博客-程序员宅基地

//point style var myIcon = L.icon({ iconUrl: 'css/images/dian.svg',// shadowUrl: 'css/images/leaf-shadow.png', iconSize: [50, 50], // size of ...

python的script目录在哪_python清除指定目录内所有文件中script的方法_知乎营销的博客-程序员宅基地

本文实例讲述了python清除指定目录内所有文件中script的方法。分享给大家供大家参考。具体如下:将脚本存储为stripscripts.py调用语法 : python stripscripts.py 使用范例 : python stripscripts.py d:\myfiles# Hello,this is a script written in Python. See http://www...

commons-pool 解析_苍穹之跃的博客-程序员宅基地

首先抛出个常见的长连接问题:   1  都知道连接MySQL的应用中大多会使用框架例如 c3p0 ,dbcp proxool 等来管理数据库连接池。 数据库连接池毫无疑问都是采用长连接方式。 那么MySQL经典八小时问题为何产生?   我一开始的疑惑是既然是长连接必然有不停的心跳检测机制一直不停的骚扰者服务端, 那么服务端怎么还能检测到一个八个小时毫无动静的连接呢? 无非是因为八个

Linux C/C++ MD5withRSA签名_yufeng20345390的博客-程序员宅基地_c++ md5withrsa

一)背景最近和一家平台厂商进行联调,他们是java后台,我们是嵌入式产品,他们要求增加http加签,之前没有相关经验,在网上一通找,最后终于测过了。二)环境这里最重要的就是openssl的版本,我是基于v1.0.0这个版本进行的验证。因为不同版本个别函数名称不一样。三)开发步骤1)openssl工具的使用 1)生成一个密钥:  openssl genrsa -out test.key 1024  这里-out指定生成文件的。需要注意的是这个文件包含了公钥和密钥两部分,也

随便推点

ios linux时间戳转时间,iOS时间戳与北京时间的转换_对不起对不起的博客-程序员宅基地

NSDateFormatter *formatter = [[NSDateFormatter alloc] init];[formatter setDateStyle:NSDateFormatterFullStyle];// 修改下面提到的北京时间的日期格式[formatter setTimeStyle:NSDateFormatterFullStyle];// 修改下面提到的北京时间的时间格式[f...

2018前端难点整理_清风细雨_林木木的博客-程序员宅基地

一、弹性盒子1.基本概念flex布局的元素称为“flex容器”,里面额子元素成员叫做“flex项目”。容器默认存在两根轴:水平的主轴(main axis)和垂直的交叉轴(cross axis)。主轴的开始位置(与边框的交叉点)叫做main start,结束位置叫做main end;交叉轴的开始位置叫做cross start,结束位置叫做cross end。项目默认沿主轴排列。单个...

计算机网络与传统多用户系统,简述计算机网络与分时多用户系统、多机系统、分布式系统区别.pdf..._曹将的博客-程序员宅基地

简述计算机网络与分时多用户系统、多机系统、分布式系统的区别一、计算机网络,是指将地理位置不同的具有独立功能的多台计算机及其外部设备,通过通信线路连接起来,在网络操作系统,网络管理软件及网络通信协议的管理和协调下,实现资源共享和信息传递的计算机系统。主要作用:1、硬件资源共享。可以在全网范围内提供对处理资源、存储资源、输入输出资源等昂贵设备的共享,使用户节省投资,也便于集中管理和均衡分担负荷。2、软...

HTTP虚拟主机_weixin_30732825的博客-程序员宅基地

Ps:http-2.4版本[[email protected] ~]# tar zxvf httpd-2.4.23.tar.gz -C /usr/src/[[email protected] ~]# cd /usr/src/httpd-2.4.23/[[email protected] httpd-2.4.23]# ./configure --prefix=/usr/local/http --enable-...

android 滚动条宽度设置,HorizontalScrollView 内动态添加控件时修改宽度适应_阿功的博客-程序员宅基地

我有一个TableLayout,它的内容是动态生成的。我遇到了下面的问题:当动态生成的一行的内容太长时,靠右边的内容会被遮住了。于是我想要这个TableLayout在横向上可以滚动。解决的办法是,用HorizontalScrollView包装TableLayout,这样,当内容很长时,就会出现横向滚动条。像这样:android:layout_width="fill_parent"android:l...

vuer路由router跳转传递参数刷新后数据无法获取_Э时间行者于我的博客-程序员宅基地

1.第一种方法 页面刷新数据会丢失我们学习过vue路由之后知道,vue传参有几种方式1.vue路由params是根据name跳转的,通过params来传递参数2.vue路由query是根据path跳转的,通过query来传递参数通过路由属性中的name来确定匹配的路由,通过params来传递参数。methods:{ toLink(id) { this.$router.push({ name: 'systemConfig', params

推荐文章

热门文章

相关标签