两个栈,一个用来存数据,一个用来存最小值。push 或者 pop的时候都要去尝试更新两个栈,变种问题是如何 O(1)取得最小值
代码格式不是很严谨,还是搞成几个典型的方法比较好
public int[] getMinStack (int[][] op) { // write code here if(op==null || op[0].length==0){ return null; } ArrayList<Integer> res=new ArrayList<>(); Stack<Integer> stack1=new Stack<>(); Stack<Integer> stack2=new Stack<>(); for(int i=0;i<op.length;i++){ int [] tmp=op[i]; if(tmp.length==2){ stack1.push(tmp[1]); if(!stack2.isEmpty()){ int top=stack2.peek(); if(top>tmp[1]){ stack2.push(tmp[1]); } }else{ stack2.push(tmp[1]); } }else { if(tmp[0]==2){ int a =stack1.peek(); int b =stack2.peek(); if(a<=b){ stack2.pop(); } stack1.pop(); }else { int a =stack2.peek(); res.add(a); } } } int [] resArray=new int [res.size()]; for(int i=0;i<res.size();i++){ resArray[i]=res.get(i); } return resArray; }