你的位置:首页 > Java教程

[Java教程]微软算法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 }