题目:
定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中调用push、pop、top、min的时间复杂度都是o(1)。
思路:
借助一个辅助栈存储最小值,这样就能在O(1)
时间内取得最小值。
代码:
public class MinStack {
Stack<Integer> mainStack = new Stack<>();
Stack<Integer> minStack = new Stack<>();//存储最小值
public void put(int node) {
mainStack.push(node);
if (minStack.empty() || node < minStack.peek()) {
minStack.push(node);
} else {
minStack.push(minStack.peek());
}
}
public void pop() {
if (!minStack.empty() && !mainStack.empty()) {
mainStack.pop();
minStack.pop();
}
}
public int min() {
if (!minStack.empty() && !mainStack.empty()) {
return minStack.peek();
}
return -1;
}
}
网友评论