题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
练习地址
https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
参考答案
import java.util.Stack;
public class Solution {
private Stack<Integer> mStack = new Stack<>();
private Stack<Integer> mMinStack = new Stack<>();
public void push(int node) {
mStack.push(node);
if (mMinStack.isEmpty() || node < mMinStack.peek()) {
mMinStack.push(node);
} else {
mMinStack.push(mMinStack.peek());
}
}
public void pop() {
if (!mStack.isEmpty()) {
mStack.pop();
mMinStack.pop();
}
}
public int top() {
return mStack.peek();
}
public int min() {
return mMinStack.peek();
}
}
复杂度分析
- 时间复杂度：O(1)。
- 空间复杂度：O(n)。
