PTA 栈 (20分)(全网首发)(实现一个栈Stack,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1))_min栈 push操作过程-程序员宅基地

技术标签: 数据结构  

题目描述:

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

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

智能推荐

SpringBoot: 浅谈文件上传和访问的坑 (MultiPartFile)_file.transferto设置文件权限-程序员宅基地

文章浏览阅读2.1k次,点赞2次,收藏4次。本次的项目环境为 SpringBoot 2.0.4, JDK8.0. 服务器环境为CentOS7.0, Nginx的忘了版本.前言SpringBoot使用MultiPartFile接收来自表单的file文件,然后进行服务器的上传是一个项目最基本的需求,我以前的项目都是基于SpringMVC框架搭建的,所以在使用SpringBoot的时候进行MultiPartFile上传遇到了坑,..._file.transferto设置文件权限

Datawhale六月学习数据分析打卡task4-程序员宅基地

文章浏览阅读87次。第三章:数据可视化学习目标:这门课程得主要目的是通过真实的数据,以实战的方式了解数据分析的流程和熟悉数据分析python的基本操作。知道了课程的目的之后,我们接下来我们要正式的开始数据分析的实战教学,完成kaggle上泰坦尼克的任务,实战数据分析全流程。 这里有两份资料需要大家准备: 图书《Python for Data Analysis》第六章和 baidu.com & google.com(善用搜索引擎)复习:复习:回顾学习完第一章,我们对泰坦尼克号数据有了基本的了解,也学到了一些基本的

【SpringBoot】浏览器报错Resource interpreted as Stylesheet but transferred with MIME type text/html-程序员宅基地

文章浏览阅读7.1w次。CSS 样式不能正常加载发现页面的样式没有显示,报错信息如下:Resource interpreted as Stylesheet but transferred with MIME type text/html: “http://localhost:8080/curd/asserts/css/signin.css”.原因之前写原生 jsp + servlet 的时候也遇到过这个问题..._resource interpreted as stylesheet

sublime text3安装emmet插件及PyV8:小白重试了n次后终于成功_emmet 的pyv8安装失败-程序员宅基地

文章浏览阅读2.7w次,点赞10次,收藏15次。标重点:是Sublime Text 3 不是2,两者的安装可能不同,小白只会3的。第一步:检查自己是否已经安装了Package Control。这一步是很关键的,安装Sublime Text时按照师兄给的步骤其实是已经将Package Control安装完成的,但是我并不清楚,后来又下载呀、安装呀乱七八糟的,间接导致了安装失败。如果安装了就是下图的样子:【图片来源:http_emmet 的pyv8安装失败

GsonUtils.java类_gsonutils.read(source, clazz)-程序员宅基地

文章浏览阅读5.5k次。import java.lang.reflect.Type;import com.google.gson.Gson;import com.google.gson.GsonBuilder;public class GsonUtils { /** * @Title: toJson * @Description: TODO(这里用一句话描述这个方法的_gsonutils.read(source, clazz)

2017-程序员宅基地

文章浏览阅读85次。#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<map>using namespace std;#define N 3struct stu { char Name[10]; int BeginHo...

随便推点

转载 Unity高阶-游戏常用设计模式_unity 高阶技术-程序员宅基地

文章浏览阅读379次。转载 原文地址https://www.jianshu.com/p/b6b92da504d1原作者:沉麟Unity高阶-游戏常用设计模式模式的诞生模式(Pattern)起源于建筑业而非软件业模式之父——美国加利佛尼亚大学环境结构中心研究所所长Christopher Alexander博士《A Pattern Language: Towns, Buildi..._unity 高阶技术

myeclipse jsp页面不提示错误_myeclipse jsp 错了没有提示-程序员宅基地

文章浏览阅读6k次。1.在项目的名字上右键单击properties,弹出properties界面2.MyEclipse—>validation—>Excluded Resource下找到不需要验证的文件或者文件夹\3.在不需要验证的文件或者文件夹前打勾,然后点击 "OK"按钮保存。我的js,jsp,html在webroot下需要注意,window---MyE_myeclipse jsp 错了没有提示

【面试宝典】Spring Cloud 系列面试题_springcloud面试宝典-程序员宅基地

文章浏览阅读1.4w次,点赞4次,收藏3次。Hystrix 是一个延迟和容错库,旨在隔离远程系统,服务和第三方库的访问点,当 出现故障是不可避免的故障时,停止级联故障并在复杂的分布式系统中实现弹性。通常对于使用微服务架构开发的系统,涉及到许多微服务。这些微服务彼此协作。假设如果上图中的微服务 9 失败了,那么使用传统方法我们将传播一个异常。但 这仍然会导致整个系统崩溃。随着微服务数量的增加,这个问题变得更加复杂。微服务的数量可以高达 1000. 这是 hystrix 出现的地方 我们将使用 Hystrix 在这种情况下的Fallback。_springcloud面试宝典

Spring security 实现前后端分离登录拦截器及用户权限控制_springsecurity 前后端分离登录-程序员宅基地

文章浏览阅读1.5w次,点赞29次,收藏103次。目录前言一、准备工作1.1、设计数据库(我的工程目录中的sql文件夹下有sql文件直接导入即可)二、代码实现2.1、数据操作2.2、自定义登录逻辑2.2.1、创建自定义UserDetailsService2.2.2、自定义的密码加密类2.3、自定义登录验证结果、登出结果、无权访问处理器2.3.1、自定义登录成功处理器2.3.2、自定义登录失败处理器2..._springsecurity 前后端分离登录

从程序员到项目经理_袭烽-程序员宅基地

文章浏览阅读4.1k次,点赞2次,收藏14次。在希腊德尔斐的阿波罗神庙上,刻得着一句神秘的箴言:“认识你自己”。从某种程度上来说,我们都是自己的“最熟悉的陌生人”。认识自己的位置,是每个人获得成长的第一堂课。一个人的位置,对其言行的影响是至关重要的,俗话说:“屁股决定脑袋”,虽然听着粗俗,却饱含人生哲理。既然我们屁股在项目经理的位置上,就应该像项目经理一样去思考问题,做事情。一.项目经理的处境经过数年的打拼,怀着美好的向往,我们终于成了他——_袭烽

linux java 屏幕分辨率,Linux全屏幕Java - 如何覆盖任务栏?-程序员宅基地

文章浏览阅读54次。I have a problem to run Java application in full screen mode on "openSUSE 11.4 (x86_64)". I am using Java 1.6.0_26-b03.I have try to run two examples of full screen application:Example from Oracle sit..._linux java full screen