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

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

` 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 }`

Top