IT公司100题-2-设计带min函数的stack
IT公司100题-2-设计带min函数的stack
关西大汉弹琵琶 发表于2年前
IT公司100题-2-设计带min函数的stack
  • 发表于 2年前
  • 阅读 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


共有 人打赏支持
粉丝 8
博文 40
码字总数 14221
评论 (2)
魔仙剑痴
真够无聊的,已经使用了java自带的栈了,该问题和算法还有何意义?
关西大汉弹琵琶

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

真够无聊的,已经使用了java自带的栈了,该问题和算法还有何意义?
美女你是几个意思? 烦请明示啊
×
关西大汉弹琵琶
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: