lintcode 中等题:Min stack 最小栈
2024-10-11 01:33:50
题目
带最小值操作的栈
实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。
你实现的栈将支持push,pop 和 min 操作,所有操作要求都在O(1)时间内完成。
解题
可以定义一个数组或者其他的存储最小值,第i个元素,表示栈中前i个元素的最小值。
定义两个ArrayList来存储栈,一个ArrayList存储当前栈中的元素,一个ArrayList存储最小栈,并且其第i个元素表示栈中前i个元素的最小值,这样两个栈的长度是始终一样的
入栈:最小栈需要加入的元素是 当前要入的元素和list中最后一个元素的最小值
出栈:最小栈也要出栈的,不需要进行比较,直接出栈
获取最小值:就是去栈顶元素的,直接取出list 中最后一个元素就好了
取栈顶元素:直接取
public class MinStack {
// 定义两个栈
private ArrayList<Integer> stack;
private ArrayList<Integer> minStack;
public MinStack() {
// do initialize if necessary
stack = new ArrayList<Integer>();
minStack = new ArrayList<Integer>();
}
// 入栈
public void push(int number) {
// write your code here
stack.add(number);
if( minStack.size() ==0){
minStack.add(number);
}else{
int size = minStack.size();
minStack.add(Math.min(number,minStack.get(size-1)));
}
}
// 出栈
public int pop() {
// write your code here
int size = minStack.size();
int pop = stack.get(size - 1);
minStack.remove(size - 1);
stack.remove(size - 1);
return pop;
}
// 最小值
public int min() {
// write your code here
int size = minStack.size();
return minStack.get(size - 1);
}
// 栈顶元素
public int peek(){
int size = stack.size();
return stack.get(size - 1);
}
}
Java Code
上面程序中最小栈元素保存的元素有重读,可以优化下。
九章中看到了另外一种解法,用两个栈了存储两个栈
一种程序如下,最小栈中重复数据减少了。
public class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
// do initialize if necessary
stack = new Stack<Integer>();
minStack = new Stack<Integer>();
} public void push(int number) {
// write your code here
stack.push(number);
if( minStack.isEmpty()){
minStack.push(number);
}else if( number <= minStack.peek()){
minStack.push(number);
}
} public int pop() {
// write your code here
int p = stack.pop();
if( p == minStack.peek())
minStack.pop();
return p;
} public int min() {
// write your code here
return minStack.peek();
}
}
Java Code
九章中给的Python版本的就是利用list实现的
class MinStack(object): def __init__(self):
# do some intialize if necessary
self.stack = []
self.minstack = [] def push(self, number):
# write yout code here
self.stack.append(number)
if len(self.minstack) == 0 or number <= self.minstack[-1]:
self.minstack.append(number) def pop(self):
# pop and return the top item in stack
if self.stack[-1] == self.minstack[-1]:
self.minstack.pop()
return self.stack.pop() def min(self):
# return the minimum number in stack
return self.minstack[-1]
Python Code
最新文章
- Python3.5 day4作业:对员工信息文件,实现增删改查操作。
- php缓冲区 sapi缓冲区
- QEMU/KVM功能测试
- c#重点[集合类型]异常,数组,集合ArrayList,List<;>;,hashTable,hashtable泛型(Dictionary)
- hdu 1115(计算多边形重心)
- linux实现nginx按照日期存储日志
- python 访问限制
- NET中的引用类型和值类型 zt
- 2D游戏编程3&mdash;GDI
- 洛谷1377 M国王 (SCOI2005互不侵犯King)
- ASP.NET MVC 5– 采用Wijmo MVC 5模板1创建应用程序分钟
- x240 uefi ubuntu 12.04.4
- 正则表达式入门案例C#
- vim8.0模式详解
- @Scope 注解
- git更新代码报错,error: The following untracked working tree files would be overwritten by ch
- node-webkit播放目录下所有网页文件
- Python使用paramiko库远程安全连接SSH
- spring mongodb增删改查操作
- Avalon探索之旅
热门文章
- !!! FAILED BINDER TRANSACTION !!! TransactionTooLargeException
- Entity Framework Code First 常用方法集成
- jsp探针
- fastclick插件 导致 input[type=";date";] 无法触发问题解决方案
- RHEL7 添加用户,含sudo权限
- jquery实现密码框显示提示文字
- TextView中gravity属性值测定
- WPF自定义控件(二)——TextBox
- 从零开始学ios开发(二十):Application Settings and User Defaults(下)
- php必看六本书