最小棧的實現(xiàn)
摘自漫畫算法:
題目:實現(xiàn)一個棧,該棧帶有出棧(pop)蔫浆、入棧(push)、取最小元素(getMin)3個方法姐叁。要保證這3個方法的時間復(fù)雜度都是O(1)瓦盛。
如圖:
圖1.png
解法步驟
1洗显、設(shè)原有的棧叫作棧A,此時創(chuàng)建一個額外的“備胎”棧B谭溉,用于輔助棧A墙懂。
解法步驟 — 圖1.png
2、當(dāng)?shù)?個元素進(jìn)入棧A時扮念,讓新元素也進(jìn)入棧B。這個唯一的元素是棧A的當(dāng)前最小值碧库。
解法步驟 — 圖2.png
3柜与、之后,每當(dāng)新元素進(jìn)入棧A時嵌灰,比較新元素和棧A當(dāng)前最小值的大小弄匕,如果小于棧A當(dāng)前最小值,則讓新元素進(jìn)入棧B沽瞭,此時棧B的棧頂元素就是棧A當(dāng)前最小值迁匠。
解法步驟 — 圖3.png
4、每當(dāng)棧A有元素出棧時驹溃,如果出棧元素是棧A當(dāng)前最小值城丧,則讓棧B的棧頂元素也出棧。此時棧B余下的棧頂元素所指向的豌鹤,是棧A當(dāng)中原本第2小的元素亡哄,代替剛才的出棧元素成為棧A的當(dāng)前最小值。
解法步驟 — 圖4.png
5布疙、每當(dāng)調(diào)用getMin方法時蚊惯,返回棧B的棧頂所存儲的值,這也是棧A的最小值灵临。
總結(jié)
顯然截型,這個解法中進(jìn)棧、出棧儒溉、取最小值的時間復(fù)雜度都是O(1)宦焦,最壞情況空間復(fù)雜度是O(n)。
代碼實現(xiàn)
import java.util.Stack;
/**
* Create By ZhangBiao
* 2020/6/5
*/
public class StackProblem {
private Stack<Integer> mainStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
/**
* 入棧操作
*
* @param element 入棧的元素
*/
public void push(int element) {
mainStack.push(element);
// 如果輔助棧為空睁搭,或者新元素小于或等于輔助棧棧頂赶诊,則將新元素壓入輔助棧
if (minStack.empty() || element <= minStack.peek()) {
minStack.push(element);
}
}
/**
* 出棧操作
*
* @return
*/
public Integer pop() {
// 如果出棧元素和輔助棧棧頂?shù)脑刂迪嗟龋o助棧出棧
if (mainStack.peek().equals(minStack.peek())) {
minStack.pop();
}
return mainStack.pop();
}
/**
* 獲取棧的最小元素
*
* @return
* @throws Exception
*/
public int getMin() throws Exception {
if (mainStack.empty()) {
throw new Exception("stack is empty");
}
return minStack.peek();
}
public static void main(String[] args) throws Exception {
StackProblem stack = new StackProblem();
stack.push(4);
stack.push(9);
stack.push(7);
stack.push(3);
stack.push(8);
stack.push(5);
System.out.println(stack.getMin());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.getMin());
}
}