题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
方案1:借助双栈来解决
import java.util.*; public class Solution { Stack<Integer> normal=new Stack(); Stack<Integer> minVal=new Stack(); public void push(int value){ if(minVal.isEmpty()||value<minVal.peek()){ minVal.push(value); }else{ minVal.push(minVal.peek()); } normal.push(value); } public void pop(){ if(!normal.isEmpty()&&!minVal.isEmpty()){ normal.pop(); minVal.pop(); } } public int top(){ int res=-1; if(!normal.isEmpty()){ res=normal.peek(); } return res; } public int min(){ int res=-1; if(!minVal.isEmpty()){ res=minVal.peek(); } return res; } }
方案2:借助栈和优先级队列来解决
import java.util.*; public class Solution { Stack<Integer> s=new Stack(); Queue<Integer> q=new PriorityQueue(); public void push(int node) { s.push(node); q.offer(node); } public void pop() { if(!s.isEmpty()){ q.remove(s.pop()); } } public int top() { if(!s.isEmpty()){ return s.peek(); } return -1; } public int min() { return q.peek(); } }