问题:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。要保证这三个方法的时间复杂度都是O(1)。
1.使用 两个栈实现
public class MinStackWithStack { public static void main(String[] args) { Student s = new Student(); s.stuAge = 28; s.stuName ="baoyou"; Student s2 = new Student(); s2.stuAge = 1; s2.stuName ="baoyuqi"; MinStack<Student> ms = new MinStack(); ms.push(s); ms.push(s2); Student min = ms.getMin(); System.out.println(min); } } class MinStack<T extends Comparable<T>>{ Stack<T> stack; Stack<T> minStack; public void push(T t){ T obj = null; if (stack == null) { stack = new Stack<T>(); minStack = new Stack<T>(); minStack.push(t); }else{ obj = minStack.peek(); if(t.compareTo(obj) >= 0){ minStack.push(obj); }else{ minStack.push(t); } } stack.push(t); } public T pop(){ if (stack == null || stack.empty()) { return null; } return stack.pop(); } public T getMin(){ if (minStack == null || minStack.empty()) { return null; } return minStack.peek(); } } class Student implements Comparable<Student>{ public String stuName; public int stuAge; @Override public int compareTo(Student s) { if (this.stuAge < s.stuAge ) { return -1; }else if(this.stuAge > s.stuAge ){ return 1; } return 0; } @Override public String toString() { return FastJsonUtils.toJSONString(this).toString(); } }
2.使用 链表实现 栈
public class MinStackUseNodeDemo { public static void main(String[] args) { Student s = new Student(); s.stuAge = 28; s.stuName = "baoyou"; Student s2 = new Student(); s2.stuAge = 1; s2.stuName = "baoyuqi"; Student s3 = new Student(); s3.stuAge = 29; s3.stuName = "baopan"; MinStackUseNode<Student> msun = new MinStackUseNode<Student>(); msun.push(s); msun.push(s2); Student min = msun.getMin(); System.out.println(min); } } class MinStackUseNode<T extends Comparable<T>> { public MinStackElem<T> top; public <T extends Comparable<T>> void push(T obj) { if (top == null) { top = new MinStackElem(obj, obj, null); } else { T min = null; if (obj.compareTo((T) top.min) >= 0) { min = (T) top.min; } else { min = obj; } MinStackElem minStackElem = new MinStackElem(obj, min, top); top = minStackElem; } } public T pop() { if (top == null) { return null; } T t = top.data; top = top.next; return t; } public T getMin() { if (top == null) { return null; } T t = top.min; return t; } } class MinStackElem<T extends Comparable<T>> { public T data; public T min; public MinStackElem next; // public MinStackNode(){} public MinStackElem(T data, T min, MinStackElem next) { this.data = data; this.min = min; this.next = next; } }
3.使用数组
public interface IMinMaxStack<T> { public T pop(); public void push(T t); public T getMin(); public T getMax(); public int getLength(); }
public class MinMaxStack implements IMinMaxStack<Integer> { private static int maxLength = 5; private static int [] data= new int[maxLength]; private static int [] mins= new int[maxLength]; private static int [] maxs= new int[maxLength]; private static int size = 0; private static int current = 0; private static int total = 0; private void growing(){ if (current >= maxLength / 4 * 3 ) { maxLength = (maxLength *3)/2 + 1; data = Arrays.copyOf(data, maxLength); mins = Arrays.copyOf(mins, maxLength); maxs = Arrays.copyOf(maxs, maxLength); } } @Override public Integer pop() { total --; if (current >= 0) { int temp = data[current-1] ; current --; return temp; } return null; } @Override public void push(Integer t) { total ++; growing(); data[current] = t; if(current == 0){ mins[current] = t; maxs[current] = t; }else{ if (mins[current-1] >= t) { mins[current] = t; }else{ mins[current] = mins[current-1]; } if (maxs[current-1] <= t) { maxs[current] = t; }else{ maxs[current] = maxs[current-1]; } } current ++; } @Override public Integer getMin() { int temp = mins[current]; return temp; } @Override public Integer getMax() { int temp = maxs[current]; return temp; } @Override public int getLength() { return total; } public static void main(String[] args) { MinMaxStack ms = new MinMaxStack(); ms.push(6); ms.push(2); ms.push(7); ms.push(1); ms.push(5); ms.push(3); System.out.println("current\tlength\tpop\tmin\tmax"); System.out.println(ms.current+"\t"+ms.getLength()+"\t"+ms.pop()+"\t"+ ms.getMin()+"\t"+ ms.getMax()); System.out.println(ms.current+"\t"+ms.getLength()+"\t"+ms.pop()+"\t"+ ms.getMin()+"\t"+ ms.getMax()); System.out.println(ms.current+"\t"+ms.getLength()+"\t"+ms.pop()+"\t"+ ms.getMin()+"\t"+ ms.getMax()); System.out.println(ms.current+"\t"+ms.getLength()+"\t"+ms.pop()+"\t"+ ms.getMin()+"\t"+ ms.getMax()); System.out.println(ms.current+"\t"+ms.getLength()+"\t"+ms.pop()+"\t"+ ms.getMin()+"\t"+ ms.getMax()); System.out.println(ms.current+"\t"+ms.getLength()+"\t"+ms.pop()+"\t"+ ms.getMin()+"\t"+ ms.getMax()); } }
捐助开发者
在兴趣的驱动下,写一个免费
的东西,有欣喜,也还有汗水,希望你喜欢我的作品,同时也能支持一下。 当然,有钱捧个钱场(支持支付宝和微信 以及扣扣群),没钱捧个人场,谢谢各位。
个人主页:http://knight-black-bob.iteye.com/
谢谢您的赞助,我会做的更好!
相关推荐
山居小栈案例分析学习教案.pptx
最小栈.md
何为最小栈?栈最基础的操作是压栈(push)和退栈(pop),现在需要增加一个返回栈内最小值的函数(get_min),要求get_min函数的时间复杂度为o(1)。python的栈肯定是使用list实现,只要将list的append和pop封装到stack类...
柚诚小栈微信小程序产品需求文档.docx
管理学案例分析 山居小栈的经营管理PPT学习教案.pptx
多线程基础介绍.........................................................................................................................................15 定义多线程术语...................................
目录 1 多线程基础介绍15 定义多线程术语15 符合多线程标准16 多线程的益处17 提高应用程序的响应 17 有效使用多处理器17 改进程序结构17 占用较少的系统资源17 结合线程和RPC(远程过程调用)18 ...
《多线程编程指南》介绍了SolarisTM操(SolarisOperatingSystem,SolarisOS中 POSIX®线程和Solaris线程的多线程编程接口。本指南将指导应用程序程序员如何创建新的多线程程序以及如何向现有的程序中添加多线程。...
文言小栈
内容来自 锋芒小栈:http://www.fongmong.com/ 联想 newifi mini 千兆路由器体验 不一般的路由器 看看 newifi mini 的真面目,主面板有电源、USB、2.4G、5G、LAN、 WAN、INTERNET 指示灯。背面铭牌写着路由器型号:R...
该程序代码,是为了准备校园招聘,或者进行算法考试的同学准备的,代码中都是一些基础算法,涉及到Leetcoder中的一些经典算法,帮助同学们快速掌握一些基础算法,在笔试面试中取得更大的优势,进入自己喜欢的公司。
LeetCode 上的题目分别是:146.LRU缓存机制 155.最小栈 225.用队列实现栈 232.用栈实现队列
15.三数之和 151.翻转字符串里的单词 152.乘积最大子数组 153.寻找旋转排序数组中的最小值 155.最小栈 169.多数元素 17.电话号码的字母组合 188.买卖股票的最佳时机IV(exception) 190.颠倒二进制位 191.位1的个数 ...
剑指offer面试题精选 剑指offer部分面试题使用javascript...面试题21:最小栈 面试题26:复杂链表的复制 面试题31:连续字数组的最大和 面试题32:从1到n的整数中1出现的次数 面试题34:丑数 面试题36:数组中的逆序对
题目分类 Hash相关 q1_两数之和 q387_字符串中的第一个唯一字符 链表操作 q2_两数相加 q19_删除链表的倒数第N个节点 q25_k个一组翻转链表 q61_旋转链表 q138_复制带随机指针的链表 q160_相交链表 ...q155_最小栈
最小栈 160. 相交链表 176. 第二高的薪水 203. 移除链表元素 206、反转链表 215. 数组中的第K个最大元素 221. 最大正方形 236. 二叉树的最近公共祖先 237. 删除链表中的节点 354. 俄罗斯套娃信封问题 393
Hash相关 q1_两数之和 q387_字符串中的第一个唯一字符 链表操作 q2_两数相加 q19_删除链表的倒数第N个节点 q25_k个一组翻转链表 q61_旋转链表 q138_复制带随机指针的链表 ...q155_最小栈 q224_基本计算
155.最小栈() () 169.求众数() () 205.同构字符串() () 206.反转链表() () 217.存在重复元素() () 231.2的幂() () 237.删除链表中的节点() () 292.Nim游戏() () 344.反转字符串() () 387.字符串中的第一个唯一字符()...