文档章节

【九度OJ1522】|【剑指offer21】包含min函数的栈

aqia358
 aqia358
发布于 2013/12/23 20:29
字数 508
阅读 153
收藏 1
题目描述:

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

输入:

输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行为一个整数n(1<=n<=1000000), n代表将要输入的操作的步骤数。
接下来有n行,每行开始有一个字母Ci。
Ci=’s’时,接下有一个数字k,代表将k压入栈。
Ci=’o’时,弹出栈顶元素。

输出:

对应每个测试案例中的每个操作,
若栈不为空,输出相应的栈中最小元素。否则,输出NULL。

样例输入:
7
s 3
s 4
s 2
s 1
o
o
s 0
样例输出:
3
3
2
1
2
3
0
解:注意首先要求是一个栈,即先进后出

解题思路:使用两个栈,一个是普通的数据栈,data,和另外一个help辅助栈,首先在空的时候都压入两个栈,然后对于压入的序列,比较 这个元素和辅助栈栈顶元素,如果小于这个栈顶那么在压入数据栈的时候也压入辅助站,否则,将辅助栈的顶部元素再次压入一次,这样保证了两个栈的大小相等, 这样才能在pop的时候同步。这样需要的空间就是两个相等的栈 。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;
/**
 * 两个栈方法
 * @author aqia358
 *
 */
public class Main {
	
	public Stack<Integer> data = new Stack<Integer>();
	public Stack<Integer> help = new Stack<Integer>();
	
	public void push(int value){
		data.push(value);
		if(help.isEmpty()){
			help.push(value);
			System.out.println(value);
		}else{
			int temp = help.peek();
			if(temp < value){
				help.push(temp);
				System.out.println(temp);
			}else{
				help.push(value);
				System.out.println(value);
			}
		}
	}
	public void pop(){
		if(help.isEmpty()){
			System.out.println("NULL");
		}else{
			data.pop();
			help.pop();
			if(help.isEmpty()){
				System.out.println("NULL");
			}else
				System.out.println(help.peek());
		}
	}

	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != StreamTokenizer.TT_EOF){
			int n = (int)st.nval;
			Main m = new Main();
			for(int i = 0; i < n; i++){
				st.nextToken();
				String op = st.sval;
				if(op.equals("s")){
					st.nextToken();
					int data = (int)st.nval;
					m.push(data);
				}else if(op.equals("o")){
					m.pop();
				}
			}
		}
	}
}



© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
私信 提问
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
[剑指offer]包含min函数的栈

题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 解题思路 用一个栈stack保存数据,用另外一个栈temp保存依次入栈最小的数 比如,stack中依次入栈 则temp依次...

繁著
2018/06/30
0
0
剑指offer 21. 包含min函数的栈

原题 定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。 Reference Answer 思路分析 思路:使用一个辅助栈保存最小值 Note: python 中 ...

dby_freedom
2018/10/21
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
2018/06/03
0
0
剑指Offer学习总结-用两个栈实现队列

剑指Offer学习总结-用两个栈实现队列 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000
2018/01/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

嵌入式应用选择合适的微控制器

为嵌入式应用选择微控制器有几个原因,即低成本,高集成度,增加可靠性,节省空间等。 准备所需硬件接口列表使用微控制器的基本硬件框图,准备一份微控制器需要支持的所有外设接口的列表。微...

linux-tao
38分钟前
4
0

中国龙-扬科
今天
2
0
使用apicloud开发移动端APP,IOS list页面滚动卡顿解决记录

给内容容器添加样式:-webkit-overflow-scrolling:touch; -webkit-overflow-scrolling:属性控制元素在移动设备上是否使用滚动回弹效果. auto:使用普通滚动, 当手指从触摸屏上移开,滚动会立即...

万建宁
今天
1
0
Akka消息传送可靠性 23

原文:https://doc.akka.io/docs/akka/2.5/general/message-delivery-reliability.html Akka可帮助您构建可靠的应用程序,这些应用程序在一台计算机中使用多个处理器核心或分布在计算机网络中...

woshixin
今天
3
0
composer安装

前言:随着开源的东西越来越多,一些好的代码我们是可以直接拿过来用的,github更是加快了这一节奏,在github上我们可以看到一些开源的项目、代码块、函数库、类结构等,我们可以直接Fork,然...

echojson
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部