题目描述:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的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
/*********************************
* 日期:2013-11-19
* 作者:SJF0115
* 题号: 题目1522:包含min函数的栈
* 来源:http://ac.jobdu.com/problem.php?pid=1522
* 结果:AC
* 来源:剑指Offer
* 总结:
**********************************/
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int MinOfStack(int n){
int i,num;
char operate;
stack<int> numStack;
stack<int> minStack;
for(i = 0;i < n;i++){
scanf(" %c",&operate);
//进栈
if(operate == 's'){
scanf("%d",&num);
numStack.push(num);
//辅助栈不空
if(!minStack.empty()){
int minNum = minStack.top();
//当前值和最小值比较,小的放入minStack
if(num < minNum){
minStack.push(num);
}
else{
minStack.push(minNum);
}
}
//辅助栈空
else{
minStack.push(num);
}
printf("%d\n",minStack.top());
}
//出栈
else if(operate == 'o'){
if(!minStack.empty()){
minStack.pop();
numStack.pop();
}
if(!minStack.empty()){
printf("%d\n",minStack.top());
}
else{
printf("NULL\n");
}
}
//非法
else{
return 0;
}
}
return 1;
}
int main()
{
int i,n;
while(scanf("%d",&n) != EOF){
int result = MinOfStack(n);
if(result == 0){
break;
}
}
return 0;
}
#include <stdio.h>
#define MAXN 1000010
int stackA[MAXN],stackB[MAXN];
int top=-1,min;
void push(int num)
{
if(top==-1){
min=num;
stackA[++top]=num;
}
else{
if(min>=num){
stackA[++top]=num;
stackB[top]=min;
min=num;
}
else
stackA[++top]=num;
}
printf("%d\n",min);
}
void pop()
{
int tmp=stackA[top--];
if(top==-1){
printf("NULL\n");
return ;
}
if(tmp==min)
min=stackB[top+1];
printf("%d\n",min);
return ;
}
int main()
{
int n,num;
char c;
while(scanf("%d",&n)!=EOF){
top=-1;
while(n--){
scanf(" %c",&c);
if(c=='s'){
scanf("%d",&num);
push(num);
}
else if(c=='o')
pop();
}
}
return 0;
}
分享到:
相关推荐
实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
剑指Offer(Python多种思路实现):包含min函数的栈 面试30题: 题目:包含min函数的栈 题:定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中,调用min、push、pop的时间复杂度都是O(1) ...
代码type MinStack struct {a []int//存储元素b []int //辅助栈 维护栈的最小值/* initialize your dat
《剑指Offer》 1. 赋值运算函数 2. 单例设计模式 3. 二维数组中查找目标值 4. 替换字符串中的空格 5. 从尾到头打印链表 6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. ...
面试题21 包含min函数的栈 面试题22 栈的压入弹出序列 面试题23 从上往下打印二叉树 面试题24 二叉树的后序遍历序列 面试题25 二叉树中和为某一值的路径 4.4 分解让复杂问题简单化 面试题26 复杂链表的复制 面试题
第二十一题 包含min函数的栈 测试21 第二十二题 判断一个栈是否是另一个栈的弹出序列 测试22 第三十三题 层序遍历二叉树 测试23 第二十四题 后序遍历二叉搜索树 测试24 第二十五题 二叉树中和为某值的路径
leetcode 2 Coding Interviews 剑指offer代码实现,通过。 # Title Solution Tag Note LeetCode 1 二维数组中的查找 数组 2 ...用两个栈实现队列 栈和队列 ...包含min函数的栈 举例让抽象具体化 21 栈
21包含min函数的栈 22栈的压入弹出序列 23从上往下打印二叉树 24二叉搜索树的后序遍历序列 25二叉树中和为某一值的路径 26复杂链表的复制 27二叉搜索树与双向链表 28字符串的排列 29数组中出现次数超过一半的数字 30...
Interviews(剑指offer Java代码)二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的最小数字斐波那契数列跳台阶变态跳台阶矩形覆盖二进制中1的个数数值的整数次方调整数组顺序使奇数...
leetcode和剑指 Algorithm Algorithm for Sword Finger,leetcode,acm....so on,please visit and give your advises please run the procedure ...剑指offer ...5.栈:用两个栈实现队列 ...20.栈:包含min函数的栈
包含min函数的栈 4、59-I. 滑动窗口 5、59-II. 队列的最大值 三、哈希表 1、03. 数组中重复的数字 2、50. 第一个只出现一次的字符 四、链表 1、18. 删除链表的节点 2、22. 链表中倒数第k个节点 3、24.反转链表 4、 ...
剑指offer在leetcode主站的对应题目。 赋值运算符函数 实现单例模式 数组中重复的数字 -> (中文版) 二维数组中的查找 -> 替换空格 -> (中文版) 从尾到头打印链表 -> (中文版) 重建二叉树 -> 暂无 用两个栈实现...
20、包含min函数的栈 21、栈的压入、弹出序列 22、从上到下打印二叉树 23、二叉搜索树的后序遍历 24、二叉树中和为某一值的路径 25、复杂链表的复制 26、二叉搜索树与双向链表 27、字符串的排列 28、数组中出现超过...
在指定空间中创建对象数组去重时间格式化获取字符串长度邮箱字符串判断颜色字符串转换字符串转为驼峰格式字符串字符统计剑指offer二维数组中的查找替换空格从尾到头打印链表重建二叉树用两个栈实现队列旋转数组的...
java lru leetcode play-leetcode Github地址 : 剑指offer(第二版) 序号 题目列表 C实现 Python实现 Java实现 学习笔记 面试题03 数组中重复的数字 面试题04 二维数组中的查找 ...用两个栈实现队列 ...包含min函数的栈