題目：定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復雜度應(yīng)為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)涣雕。
