定義棧的數(shù)據(jù)結(jié)構(gòu)每聪，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中翻斟，調(diào)用 min晓锻、push 及 pop 的時間復(fù)雜度都是 O(1)
解題思路
需要兩個棧, 一個保存數(shù)據(jù), 一個保存每一次將元素壓入棧后的當(dāng)前最小值
壓入元素時, dataStack正常壓入, minStack則壓入要壓入的元素和minStack棧頂之間的最小值Math.min(x, minStack.element())
彈出元素則兩個棧都正常彈出
得到棧的最小值則只需要查看minStack的棧頂元素即可
代碼
class MinStack {
Deque<Integer> dataStack;
Deque<Integer> minStack;
public MinStack() {
dataStack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int x) {
dataStack.push(x);
if (minStack.isEmpty()) {
minStack.push(x);
} else {
minStack.push(Math.min(x, minStack.element()));
}
}
public void pop() {
if (!dataStack.isEmpty()) {
dataStack.pop();
minStack.pop();
}
}
public int top() {
if (!dataStack.isEmpty()) {
return dataStack.element();
} else {
return 0;
}
}
public int min() {
if (!minStack.isEmpty()) {
return minStack.element();
} else {
return 0;
}
}
}
