劍指 Offer 30. 包含min函式的堆疊(雙堆疊實作彈出最小值)
定義堆疊的資料結構，請在該型別中實作一個能夠得到堆疊的最小元素的 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.
解題思路:
需要兩個堆疊，一個真正的堆疊，和一個輔助記錄最小值的堆疊
函式設計：
push(x) 函式： 重點為保持堆疊 BB 的元素是 非嚴格降序 的，
將 xx 壓入堆疊 AA （即 A.add(x) ）；
若 ① 堆疊 BB 為空 或 ② xx 小于等于 堆疊 BB 的堆疊頂元素，則將 xx 壓入堆疊 BB （即 B.add(x) ），
pop() 函式： 重點為保持堆疊 A, BA,B 的 元素一致性 ，
執行堆疊 AA 出堆疊（即 A.pop() ），將出堆疊元素記為 yy ；
若 yy 等于堆疊 BB 的堆疊頂元素，則執行堆疊 B 出堆疊（即 B.pop() ），
top() 函式： 直接回傳堆疊 AA 的堆疊頂元素即可，即回傳 A.peek() ，
min() 函式： 直接回傳堆疊 BB 的堆疊頂元素即可，即回傳 B.peek() ，
class MinStack {
Stack<Integer> A, B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.add(x);
if(B.empty() || B.peek() >= x)
B.add(x);
}
public void pop() {
if(A.pop().equals(B.peek()))
B.pop();
}
public int top() {
return A.peek();
}
public int min() {
return B.peek();
}
}
解題出自力扣
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/230644.html
標籤：其他