LCOF 30. 包含min函数的栈
1. 问题
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示:
各函数的调用总次数不超过 20000 次
2. 解法
2.1 Java
class MinStack {
/**
* A为主栈,用于存储所有的元素
* B为辅助栈,用于存储最小数
*/
Stack<Integer> stackA, stackB;
// 对两个栈进行初始化
public MinStack() {
stackA = new Stack<>();
stackB = new Stack<>();
}
public void push(int x) {
stackA.push(x);
// 如果B为空,或者x比B的栈顶元素小,就把x压入B栈
if (stackB.empty() || x <= stackB.peek())
stackB.push(x);
}
public void pop() {
// 如果A的栈顶元素和B的栈顶元素(即当前的最小数)一致,那么A和B一起pop
// 如果不一致,只要pop栈A中的栈顶元素即可,因为最小数此时没有发生改变
// 注意:这里要用「equals」不能用「==」,仅当整数值处于[-128,127]之间可以使用「==」比较
if (stackA.pop().equals(stackB.peek()))
stackB.pop();
}
public int top() {
return stackA.peek();
}
public int min() {
return stackB.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
2.2 Kotlin
class MinStack {
/**
* A为主栈,用于存储所有的元素
* B为辅助栈,用于存储最小数
*/
var stackA: Stack<Int>
var stackB: Stack<Int>
// 对两个栈进行初始化
init {
stackA = Stack()
stackB = Stack()
}
fun push(x: Int) {
stackA.push(x)
// 如果B为空,或者x比B的栈顶元素小,就把x压入B栈
if (stackB.empty() || x <= stackB.peek())
stackB.push(x)
}
fun pop() {
// 如果A的栈顶元素和B的栈顶元素(即当前的最小数)一致,那么A和B一起pop
// 如果不一致,只要pop栈A中的栈顶元素即可,因为最小数此时没有发生改变
if (stackA.pop() == stackB.peek())
stackB.pop()
}
fun top(): Int {
return stackA.peek()
}
fun min(): Int {
return stackB.peek()
}
}
/**
* Your MinStack object will be instantiated and called as such:
* var obj = MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.min()
*/
2.3 复杂度分析
时间复杂度
O(1)
: push(), pop(), top(), min() 四个函数的时间复杂度都属于常数级别。空间复杂度
O(N)
:辅助栈 B 最差情况下存储 N 个元素,需要使用O(N)
的额外空间。
3. 参考
最后更新于
这有帮助吗?