文档章节

IT公司100题-2-设计带min函数的stack

关西大汉弹琵琶
 关西大汉弹琵琶
发布于 2015/10/20 17:35
字数 280
阅读 66
收藏 6

问题描述:

定义栈的数据结构,要求添加一个min 函数,能够得到栈的最小元素。

要求函数min、push 以及pop 的时间复杂度都是O(1)。

 

双倍空间实现:

保存2个栈,分别是元素和当前最小值。

 

压缩空间实现:

代码实现:

package oschina.IT100;
/**
 * @project: oschina
 * @filename: IT2.java
 * @version: 0.10
 * @author: JM Han
 * @date: 17:08 2015/10/20
 * @comment: design a stack that has min function which could return the min element at anytime
 * @result:
 */

import java.util.Stack;

class MinStack{
   Stack<Integer> stacks, mins;
   MinStack(){
      stacks = new Stack<Integer>();
      mins   = new Stack<Integer>();
   }
   void push(Integer x){
      stacks.push(x);
      //use <= instead of < for duplicate element
      if(mins.isEmpty() || x <= mins.peek())
         mins.push(x);
   }
   void pop(){
      Integer x = stacks.pop();
      if(x == mins.peek())
         mins.pop();
   }
   Integer peek(){
      return stacks.peek();
   }
   Integer getMin(){
      return mins.peek();
   }
}

public class IT2 {
   public static void main(String[] args) {
      MinStack minStack = new MinStack();
      minStack.push(6);
      minStack.push(2);
      minStack.push(3);
      minStack.push(1);
      minStack.push(1);
      minStack.push(5);
      minStack.push(8);
      System.out.println("Content of stack: \n" + minStack.stacks);
      System.out.println("min value of stack: \n" + minStack.getMin());
      System.out.println("Content of mins: \n" + minStack.mins);
      minStack.pop();
      minStack.pop();
      minStack.pop();
      System.out.println("Content of mins: \n" + minStack.mins);
      System.out.println("min value of stack: \n" + minStack.getMin());
   }
}

 输出:

Content of stack: 
[6, 2, 3, 1, 1, 5, 8]
min value of stack: 
1
Content of mins: 
[6, 2, 1, 1]
Content of mins: 
[6, 2, 1]
min value of stack: 
1


© 著作权归作者所有

共有 人打赏支持
关西大汉弹琵琶
粉丝 7
博文 41
码字总数 14221
作品 0
浦东
程序员
私信 提问
加载中

评论(2)

关西大汉弹琵琶
关西大汉弹琵琶

引用来自“為妳變┳乖”的评论

真够无聊的,已经使用了java自带的栈了,该问题和算法还有何意义?
美女你是几个意思? 烦请明示啊
魔仙剑痴
真够无聊的,已经使用了java自带的栈了,该问题和算法还有何意义?
重磅分享:微软等数据结构+算法面试100题全部答案完整亮相

引言 无私分享造就开源的辉煌。 今是二零一一年十月十三日,明日14日即是本人刚好开博一周年。在一周年之际,特此分享出微软面试全部100题答案的完整版,以作为对读者的回馈。 一 年之前的1...

云栖希望。
2017/12/10
0
0
GitHub上11月份最热门的Java项目

又到了公布 GitHub 上热门项目的时候啦~在 11 月的排行中,猿妹加入非软件类的项目,这样可以帮助大家更直观的了解哪些项目才是GitHub 上最热门的。现在,一起来看看这些项目你使用过哪些呢?...

架构之路
2017/12/05
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0
[LeetCode] Max Stack 最大栈

Design a max stack that supports push, pop, top, peekMax and popMax. push(x) -- Push element x onto stack. pop() -- Remove the element on top of the stack and return it. top() -......

机器的心脏
2017/12/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

手写一个重试机制程序(使用Callable)

java.util.concurrent.Callable<V>接口可以实现多线程,同时还能实现一个简易重试机制。 查看Callable接口源码可知,它内部的call()方法带返回值,同时抛出了异常。 public interface Cal...

哥本哈根的小哥
6分钟前
0
0
能否通过反射修改被 final 修饰的成员变量?

一、背景 日常磨刀 二、阅前须知知识点: 当final修饰的成员变量在定义的时候初始化值,反射就不能动态修改它的值了。 当final修饰的成员变量在定义的时候没有初始化值,就还能通过反射来动态...

jack__0023
24分钟前
0
0
方之熙博士被任命为RISC-V基金会中国顾问委员会主席,加速RISC-V ISA在中国的应用

中国顾问委员会将就RISC-V基金会的教育和应用推广战略提供指导 今天在中国乌镇举行的世界互联网大会(World Internet Conference)上,RISC-V基金会(RISC-V Foundation)宣布,半导体行业资深人...

whoisliang
38分钟前
1
0
为了用户体验,不要做浏览器兼容

读者看到这篇文章的标题也许会感到奇怪,按照通常的经验来说,为了用户体验应该做浏览器兼容,以便让不同的浏览器用户都能有好的体验,从而增加网站的流量,但是我认为做浏览器兼容属于同样的...

Bob2100
38分钟前
1
0
分布式定时任务架构 (二) xxl-job二次开发实践

4个月前,公司有任务调度的需求,需要一周内完成,时间非常紧。 需求有三点: web界面编辑cron表达式,启动,停止任务 接入公司的rpc成本较低,公司有自研的rpc,研发人员希望共用同一套注解 ...

勇哥和你一起学技术
55分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部