微软算法100题02 设计包含min函数的栈

来源:转载

要求:

1. 定义栈的数据结构,要求添加一个 min函数,能够得到栈的最小元素2. 要求函数 min、push 以及 pop 的时间复杂度都是 O(1)

 

思路: 构建一个辅助栈, 只有当前入栈的数据小于该辅助栈的栈顶元素时,才将其push到辅助栈, 保证辅助栈的栈顶元素总为最小,当出栈时,如果出栈元素大于辅助栈栈顶元素,则该元素必然不在辅助栈中,因为辅助栈保留了原始栈的入栈顺序(只按大到小存储 舍弃了一些元素), 该较大元素在入栈时就已经被辅助栈过滤掉了,如果出栈元素小于或等于辅助栈栈顶元素,则辅助栈也进行pop操作

 

 1 package com.rui.microsoft; 2 3 import java.util.Stack; 4 5 public class Test02_MinStack { 6 7 public static void main(String[] args) { 8 MyStack myStack = new MyStack(); 9 myStack.push(5);10 myStack.push(3);11 myStack.push(1);12 myStack.push(6);13 14 System.out.println(myStack.min());15 16 myStack.pop();17 System.out.println(myStack.min());18 19 myStack.pop();20 System.out.println(myStack.min());21 22 }23 24 static class MyStack{25 private Stack<Integer> stack = new Stack<Integer>();26 private Stack<Integer> minStack = new Stack<Integer>();27 28 public void push(int i){29 stack.push(i);30 31 if(minStack.isEmpty()){32 minStack.push(i);33 }else{34 int min = minStack.peek();35 //minStack only push item smaller than its top item36 //minStack只入栈比其栈顶元素小的元素37 if(i < min){38 minStack.push(i);39 }40 }41 }42 43 public Integer pop(){44 Integer i = stack.pop();45 //when pop an item from original stack46 //we need to process the minStack also47 //if the item popped from original stack is larger than minStack's top item48 //it means this item should not exist in minStack49 if(i <= minStack.peek()){50 minStack.pop();51 }52 return i;53 }54 55 public Integer min(){56 return minStack.peek();57 }58 }59 }

 



分享给朋友:
您可能感兴趣的文章:
随机阅读: