題目描述
最小棧
設(shè)計一個支持 push 灵巧，pop 搀矫，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧刻肄。
push(x) —— 將元素 x 推入棧中瓤球。
pop() —— 刪除棧頂?shù)脑亍?br>
top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素敏弃。
示例:
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]
解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
數(shù)據(jù)結(jié)構(gòu)
- 數(shù)組（棧）卦羡、鏈表（鏈棧）
算法思維
- 遍歷、狀態(tài)機麦到、快照绿饵、棧特性（LIFO）
解題要點
- 使用快照記錄狀態(tài)信息
- 利用棧的 LIFO 特性，實現(xiàn)狀態(tài)信息的 更新/回滾
解題思路
一. Comprehend 理解題意
- 需要自實現(xiàn)一個棧結(jié)構(gòu)
- 除了基礎(chǔ)的入棧瓶颠、出棧拟赊、查看棧頂功能外，還需要實現(xiàn)一個查詢最小值的功能
二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法
解法一：使用數(shù)組實現(xiàn)棧結(jié)構(gòu)粹淋，棧的最小值通過遍歷數(shù)組獲得
- 數(shù)據(jù)結(jié)構(gòu)：數(shù)組
- 算法思維：遍歷
三. Code 編碼實現(xiàn)基本解法
class MinStack {
//1.聲明存放數(shù)據(jù)的數(shù)組和棧頂指針
Integer[] arr;
int index;
/**
* initialize your data structure here.
*/
public MinStack() {
//2.構(gòu)造器中進行參數(shù)初始化
arr = new Integer[1000];
index = -1;
}
public void push(int x) {
//3.入棧 -- 自動裝箱
arr[++index] = x;
//數(shù)組擴容
if (index == arr.length*0.8){
Integer[] arr1 = new Integer[arr.length*2];
for (int i=0; i<arr.length; i++){
arr1[i] = arr[i];
}
arr = arr1;
}
}
public void pop() {
if(index < 0) return;
//4.出棧 -- 相當(dāng)于刪除棧頂元素 -- 棧頂賦值為 null
arr[index--] = null;
}
public int top() {
if (index < 0) return Integer.parseInt(null);
//5.返回棧頂元素 -- 自動拆箱
return arr[index];
}
public int getMin() {
if (index < 0) return Integer.parseInt(null);
//6.遍歷數(shù)組尋找最小值
int minus = arr[0]; //最小值
for (int i=1; i<=index; i++){
minus = arr[i] < minus ? arr[i] : minus;
}
return minus;
}
}
執(zhí)行耗時：65 ms吸祟，擊敗了 7.35% 的Java用戶
內(nèi)存消耗：40.2 MB，擊敗了 55.30% 的Java用戶
時間復(fù)雜度：O(n) -- 數(shù)組的遍歷 O(n)桃移，數(shù)組的擴容 O(n)
空間復(fù)雜度：O(n) -- 數(shù)組的內(nèi)存空間 O(n)
四. Consider 思考更優(yōu)解
改變算法思維屋匕！
思路：
- 每次獲取最小值時，都需要重新 遍歷 數(shù)組借杰，效率很低
- 不難發(fā)現(xiàn)过吻，每個元素在被壓入棧頂?shù)臅r候，棧的最小值都只有 兩種狀態(tài) ：
1.當(dāng)前元素為最小值（狀態(tài)一：某個新的數(shù)值）
2.以前的最小值仍為最小值（狀態(tài)二：原數(shù)值） - 能否利用棧的特性第步，彈出棧頂元素的時候疮装，將最小值的狀態(tài)變化也一并彈出缘琅？
方法：
- 讓每個元素都攜帶一個“快照”，記錄此元素入棧后（這一時刻）棧的最小值廓推。
- 當(dāng)前棧的最小值 == 當(dāng)前棧頂元素快照中的值
- 當(dāng)棧頂元素被彈出刷袍，上個元素成為棧頂，上個快照被啟用樊展，最小值回滾
解法二：使用鏈表實現(xiàn)棧結(jié)構(gòu)呻纹，棧的最小值由棧頂元素攜帶
- 數(shù)據(jù)結(jié)構(gòu)：鏈表（鏈棧）
- 算法思維：狀態(tài)機、快照专缠、棧特性（LIFO）
五. Code 編碼實現(xiàn)最優(yōu)解
class MinStack {
//1.聲明一個內(nèi)部類 -- 鏈表節(jié)點
private class Node{
int val; //當(dāng)前節(jié)點值
int min; //最小值快照 -- 當(dāng)前節(jié)點入棧后雷酪，棧的最小值
Node next; //指針
public Node(){}
public Node(int val, int min, Node next){
this.val = val;
this.min = min;
this.next = next;
}
}
//2.聲明一個鏈表頭 -- 棧頂
Node head;
/**
* initialize your data structure here.
*/
public MinStack() {
//3.初始化鏈棧
head = null;
}
public void push(int x) {
//4.節(jié)點入棧時，判斷鏈表長度
if (head == null) {
head = new Node(x,x,null);
} else {
//5.每次入棧時涝婉，比較最小值哥力，將此刻的最小值存入 new Node().min 中
head = new Node(x,Math.min(x,head.min),head);
}
}
public void pop() {
//6.出棧時，直接彈出即可墩弯，最小值隨之回滾
if (head != null) head = head.next;
}
public int top() {
//7.查棧頂
return head != null ? head.val : Integer.parseInt(null);
}
public int getMin() {
//8.查最小值 -- 其實就是查當(dāng)前棧頂?shù)淖钚≈悼煺? return head != null ? head.min : Integer.parseInt(null);
}
}
執(zhí)行耗時：6 ms吩跋，擊敗了 96.02% 的Java用戶
內(nèi)存消耗：40.3 MB，擊敗了 36.21% 的Java用戶
時間復(fù)雜度：O(1) -- 棧頂元素的直接查詢 O(1)
空間復(fù)雜度：O(n) -- 鏈棧的內(nèi)存空間 O(n)
六. Change 變形與延伸
=== 待續(xù) ===
