原文:
How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.
译文:
实现一个栈,除了push和pop操作,还要实现min函数以返回栈中的最小值。 push,pop和min函数的时间复杂度都为O(1)。
用一个额外的栈保存最小值,push时,如果要push的值小等于当前最小值,则也push到最小栈中。
pop时,如果pop出的值等于当前最小值,则也把当前最小值pop出。
package Stack_Queue;
import java.util.Stack;
public class S3_2 {
static Stack<Integer> min = new Stack<Integer>();
static Stack<Integer> stack = new Stack<Integer>();
// 如果要push的值小等于当前最小值,则也push到最小栈中
public static void push(int data) {
stack.push(data);
if(min.isEmpty() || data<=min.peek()) {
min.push(data);
}
}
// 如果pop出的值等于当前最小值,则也把当前最小值pop出
public static int pop() {
int res = stack.pop();
if(res == min.peek()) {
min.pop();
}
return res;
}
public static int getMin() {
return min.peek();
}
public static void main(String[] args) {
push(2);
push(6);
push(4);
push(1);
push(5);
System.out.println(getMin());
pop();
System.out.println(getMin());
pop();
System.out.println(getMin());
pop();
System.out.println(getMin());
pop();
System.out.println(getMin());
pop();
}
}
分享到:
相关推荐
包含min函数的栈(The_stack_containing_the_min_function.java) 队列的最大值(The_maximum_value_of_the_queue.java) 堆(heap_items) 最小的k个数(The_smallest_k_number.java) 位运算(bit_...
面试题54-二叉搜索树的第k大节点Stack & Queue面试题09-用两个栈实现队列面试题30-包含min函数的栈面试题31-栈的压入、弹出序列面试题58-
一、stack 堆栈 5 成员函数: 5 实例程序: 5 二、queue 队列 6 成员函数: 6 实例程序: 6 三、Priority Queues 优先队列 7 成员函数: 7 实例程序: 7 四、Bitset位集合 9 成员函数: 9 实例程序: 9 五、list ...
4.2 C++ STL的各种实现版本 49 4.2.1 HP STL 49 4.2.2 SGI STL 50 4.2.3 STLport 50 4.2.4 P.J.Plauger STL 50 4.2.5 Rouge Wave STL 50 4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 ...
4.2 C++ STL的各种实现版本 49 4.2.1 HP STL 49 4.2.2 SGI STL 50 4.2.3 STLport 50 4.2.4 P.J.Plauger STL 50 4.2.5 Rouge Wave STL 50 4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 ...
4.2 C++ STL的各种实现版本 49 4.2.1 HP STL 49 4.2.2 SGI STL 50 4.2.3 STLport 50 4.2.4 P.J.Plauger STL 50 4.2.5 Rouge Wave STL 50 4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 ...
实现堆栈和队列 - StackQueue.java 使用 min 函数实现堆栈 - StackWithMin.java 桶排序 - bucketSort.java finobacci 序列 - fibonacci.java 查找树是否平衡 - isBalanced.java 实现归并排序 - merge
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、RB-tree的实现、hash-table的实现、set/map 的实现;你将看到各种算法(排序、搜寻、排列组合、数据移动与复制…)的实现;你甚至将...
第7章 仿函数(functor,另名 函数对象function objects) 413 7.1 仿函数(functor)概观 413 7.2 可配接(adaptable)的关键 415 7.2.1 unary_function 416 7.2.2 binary_function 417 7.3 算术类...
20.4.1 stack适配器 20.4.2 queue适配器 20.4.3 Priority_queue适配器 20.5 算法 20.5.1 fill、fill_n、generate与generate_n 20.5.2 equal、mismatch和1exicographical_compare 20.5.3 remove、remove...
20.4.1 stack适配器 20.4.2 queue适配器 20.4.3 Priority_queue适配器 20.5 算法 20.5.1 fill、fill_n、generate与generate_n 20.5.2 equal、mismatch和1exicographical_compare 20.5.3 remove、remove...
3.2.5 抛出标准异常和实现自己的异常 8 3.3 配置器 8 4 通用工具 9 4.1 简介 9 4.1.1 类别 9 4.1.2 头文件 9 4.2 Pairs 9 4.2.1 简介 9 4.2.2 示例 9 4.3 auto_ptr 10 4.3.1 作用 10 4.3.2 引入原因 10 4.3.3 声明 ...
单链表实现和最常用的函数 [] Double Linked List - 双链表实现[] Queue - 使用双链表的队列实现 [] Stack - 自定义 JS 堆栈实现 [] Graph - JS Graph 实现 [] Binary Tree - JS 使用树节点的二叉树实现 [] Binary ...
栈的基本操作 Stack 递推法求解无符号第一类斯特林数 Stirling-Number(Cycle,Unsigned,Recursion) 递推法求解第二类斯特林数 Stirling-Number(Subset,Recursion) 倍增法求解后缀数组 Suffix-Array(Doubling) ...
包含的数据结构存储桶还包括用于操纵多个函数。支持平台每个台式机和移动浏览器(包括IE6) Node.js 如果支持JavaScript,则可能支持存储桶。下载存储桶直接下载 (用于开发)或 (用于生产) 然后,将其作为脚本...
1.5.17 Queue类——队列 115 1.5.18 Remove方法——移除指定项 116 1.5.19 RemoveAt方法——移除指定索引处的项 118 1.5.20 Replace方法——替换文件或字符串 119 1.5.21 Reverse方法——反转数组元素 120 1.5.22 ...