文档章节

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

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

问题描述:

定义栈的数据结构,要求添加一个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
微软等公司数据结构+算法面试100题

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

chambai
2012/08/05
0
0
GitHub上11月份最热门的Java项目

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

架构之路
2017/12/05
0
0
百度3道算法题求解

第一题: 某个公司举行一场羽毛球赛,有1001个人参加,现在为了评比出“最厉害的那个人”,进行淘汰赛,请问至少需要进行多少次比赛。 第二题 有100个灯泡,第一轮把所有灯泡都开启,第二轮把...

u011729265
2015/05/31
0
0
算法3-设计包含min函数的栈

题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 思路:使用一个辅助栈来保存最小元素,这个解法简单不失优雅。设该...

kuanshang
2014/03/06
0
0
(转)十月百度,阿里巴巴,迅雷搜狗最新面试七十题

(转)十月百度,阿里巴巴,迅雷搜狗最新面试十一题 来自:http://blog.csdn.net/vjulyv/article/details/6855788 引言 当即早已进入10月份,十一过后,招聘,笔试,面试,求职渐趋火热。而在这...

idea_biu
2011/10/20
0
1
[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
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

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

云栖希望。
2017/12/04
0
0
openssl中的STACK操作实现了一个自动增加的堆栈

利用STACKOF宏可以快速实现一个自动增长的堆栈,由于堆栈可以作为一个数组来使用,所以OpenSSL中很多地方都使用了。STACKOF宏来实现大小不固定的数组。 typedef struct stackst { int num; ...

晨曦之光
2012/04/10
537
0
[BZOJ1497][NOI2006]最大获利(最大权闭合子图)

原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1497 Description 新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一...

CABI_ZGX
2017/11/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
9
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
4
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
172
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0
开发技术瓶颈期,如何突破

前言 读书、学习的那些事情,以前我也陆续叨叨了不少,但总觉得 “学习方法” 就是一个永远在路上的话题。个人的能力、经验积累与习惯方法不尽相同,而且一篇文章甚至一本书都很难将学习方法...

_小迷糊
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部