文档章节

【九度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) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

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

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

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

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

dby_freedom
10/21
0
0
python剑指offer66题

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

lyy0905
06/03
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Confluence 6 教程:在 Confluence 中导航

当你对 Confluence 有所了解后,你会发现 Confluence 使用起来非常简单。这个教程主要是针对你使用的 Confluence 界面进行一些说明,同时向你展示在那里可以进行一些通用的任务和操作。 空间...

honeymose
13分钟前
2
0
sed, awk 练习

1. sed打印某行到某行之间的内容 2. sed 转换大小写 将单词首字母转化大写 将所有小写转化大写 3. sed 在某一行最后面添加一个数字 4. 删除某行到最后一行 解析: {:a;N;$!ba;d} :a : 是...

Fc丶
今天
2
0
babel6升级到7,jest-babel报错:Requires Babel "^7.0.0-0", but was loaded with "6.26.3".

自从将前端环境更新到babel7,jest-babel之前是基于babel6的,执行时候就会报:Requires Babel "^7.0.0-0", but was loaded with "6.26.3". 很烦,因为连续帮好几台电脑修复这个问题,所以记...

曾建凯
今天
1
0
探索802.11ax

802.11ax承诺在真实条件下改善峰值性能和最差情况。 如何改善今天的Wi-Fi? 在决定如何改进当前版本以外的Wi-Fi时,802.11ac,IEEE和Wi-Fi联盟调查了Wi-Fi部署和行为,以确定更广泛使用的障碍...

linuxprobe16
今天
2
0
使用linux将64G的SDCARD格式化为FAT32

一、命令如下: sudo fdisk -lsudo mkfs.vfat /dev/sda -Isudo fdisk /dev/sda Welcome to fdisk (util-linux 2.29.2). Changes will remain in memory only, until you decide to wri......

mbzhong
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部