摘要:题目实现一个特殊的栈,在实现栈的基本功能上再实现一个实现返回栈中最小元素的操作。要求,操作的时间复杂度都是,设计的栈类型额可以使用现成的栈结构。第一种代码实现第二种代码实现
【题目】实现一个特殊的栈,在实现栈的基本功能上再实现一个实现返回栈中最小元素的操作。
【要求】
1,pop、push、getMin操作的时间复杂度都是O(1);
2,设计的栈类型额可以使用现成的栈结构。
第一种代码实现:
public class GetMinStack_1 { private StackstackData; private Stack stackMin; public GetMinStack_1(){ stackData = new Stack (); stackMin = new Stack (); } public void push(int newNum){ if (stackMin.isEmpty()) { stackMin.push(newNum); }else if (newNum <= getMin()) { stackMin.push(newNum); } stackData.push(newNum); } public int pop(){ if (stackData.isEmpty()) { System.out.println("stack is empty"); return -1; } int value = stackData.pop(); if (value == getMin()) { stackMin.pop(); } return value; } private int getMin() { // TODO Auto-generated method stub if (stackMin.isEmpty()) { System.out.println("stack is empty"); return -1; } return stackMin.peek(); } public static void main(String[] args) { // TODO Auto-generated method stub GetMinStack_1 stack = new GetMinStack_1(); int[] testNum = {4,2,4,6,5,0,1,10}; for(int i:testNum){ stack.push(i); } for(int i = 0; i < testNum.length; i++){ System.out.println(stack.getMin()+" "+stack.pop()); } } }
第二种代码实现 :
public class GetMinStack_2 { private StackstackData; private Stack stackMin; public GetMinStack_2(){ stackData = new Stack (); stackMin = new Stack (); } public void push(int newNum){ if (stackMin.isEmpty()) { stackMin.push(newNum); } else if (newNum <= getMin()) { stackMin.push(newNum); }else { stackMin.push(getMin()); } stackData.push(newNum); } public int pop(){ if (stackData.isEmpty()) { System.out.println("stack is empty"); return -1; } int value = stackData.pop(); stackMin.pop(); return value; } private int getMin() { // TODO Auto-generated method stub if (stackMin.isEmpty()) { System.out.println("stack is empty"); return -1; } return stackMin.peek(); } public static void main(String[] args) { // TODO Auto-generated method stub GetMinStack_2 stack = new GetMinStack_2(); int[] testNum = {4,2,4,6,5,0,1,10}; for(int i:testNum){ stack.push(i); } for(int i = 0; i < testNum.length; i++){ System.out.println(stack.getMin()+" "+stack.pop()); } } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65579.html
摘要:题目描述设计一个支持,,操作,并能在常数时间内检索到最小元素的栈。删除栈顶的元素。检索栈中的最小元素。示例返回返回返回代码实现 题目描述 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 示例...
摘要:删除栈顶的元素。可以另外新建一个栈来顺序存入数据最小值。另外在数据入栈时需要判断该值是否比辅助栈的栈顶元素的值更小,如果更小,也应该将它加入辅助栈。并且需要判断辅助栈是否为空,在不空的条件下才可以取栈顶元素比较,否则会溢出。 LeetCode 155:最小栈 Min Stack 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) -- ...
摘要:总结的时间复杂度是,是空间是使用辅助栈来存储最小值。项目就是为了解决配置繁琐的问题,最大化的实现约定大于配置。 前言 只有光头才能变强 Redis目前还在看,今天来分享一下我在秋招看过(遇到)的一些面试题(相对比较常见的) 0、final关键字 简要说一下final关键字,final可以用来修饰什么? 这题我是在真实的面试中遇到的,当时答得不太好,现在来整理一下吧。 final可以修饰...
摘要:题目地址题目描述设计一个支持,,操作,并能在常数时间内检索到最小元素的栈。将元素推入栈中。删除栈顶的元素。示例返回返回返回解答每次入栈都放入两个元素,分别是当前元素,和当前的最小元素因此放入之前需要和当前值进行比较。 题目地址:https://leetcode-cn.com/probl...题目描述:设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 p...
阅读 3856·2021-11-16 11:50
阅读 883·2021-11-11 16:55
阅读 3608·2021-10-26 09:51
阅读 807·2021-09-22 15:03
阅读 3328·2019-08-30 15:54
阅读 3239·2019-08-30 15:54
阅读 2439·2019-08-30 14:04
阅读 888·2019-08-30 13:53