要求：
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 }
原标题：微软算法100题02 设计包含min函数的栈
关键词：微软
我知道了 