`
standalone
  • 浏览: 609814 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

stack with min operation

 
阅读更多
How would you design a stack which, in addition to push and pop, also has a function
min which returns the minimum element? Push, pop and min should all operate in
O(1) time.


public class StackWithMin extends Stack<NodeWithMin> {
public void push(int value) {
int newMin = Math.min(value, min());
super.push(new NodeWithMin(value, newMin));
}
}
public int min() {
	
if (this.isEmpty()) {
		
return Integer.MAX_VALUE;
	
} else {
		
return peek().min;
	
}
}
class NodeWithMin {
public int value;
public int min;
public NodeWithMin(int v, int min){
value = v;
this.min = min;
}
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics