前面我們學(xué)習(xí)了很多關(guān)于棧的知識(shí)，比如《動(dòng)圖演示：手?jǐn)]堆棧的兩種實(shí)現(xiàn)方法！》和《JDK 竟然是這樣實(shí)現(xiàn)棧的？》，那么接下來(lái)我們?cè)賮?lái)刷一些關(guān)于棧的經(jīng)典面試題以鞏固學(xué)過(guò)的知識(shí)。
我們今天的面試題是這樣的...
題目
定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 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.
LeetCode 地址：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
思考
首先來(lái)說(shuō)這道題目本身很好理解，它的實(shí)現(xiàn)難點(diǎn)在于以下兩個(gè)方面：
- 當(dāng)我們進(jìn)行 pop（移除棧頂元素）操作時(shí)如果刪除的是當(dāng)前最小值，那么我們?nèi)绾螌ふ蚁乱粋€(gè)最小值？
- 要保證調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 O(1)。
也就是說(shuō)，在我們執(zhí)行了 pop 時(shí)如果移除的棧中最小的值，那么如何尋找棧中的下一個(gè)最小元素？并且要保證操作的時(shí)間復(fù)雜度為 O(1)。這個(gè)時(shí)間復(fù)雜度制約了我們?cè)谝瞥俗钚≈抵蟛荒芡ㄟ^(guò)遍歷查找下一個(gè)最小值，所以這就成為了這道題的難點(diǎn)。
比如當(dāng)我們移除以下棧頂元素值：
因?yàn)樽钚≈稻褪?1，因此在移除之后最小值也被移除了，如下圖所示：
那么接下來(lái)，讓我們一起思考 3 分鐘，想一想應(yīng)該如何處理這個(gè)問(wèn)題~
解題思路
其實(shí)我們可以在每次入棧時(shí)，判斷當(dāng)前元素是否小于最小值，如果小于則將原最小值和最新的最小值相繼入棧，這樣在調(diào)用 pop 時(shí)即使移除的是最小值，我們也能通過(guò)獲取下一個(gè)元素得到一個(gè)新的最小值，執(zhí)行流程如下所示。
操作步驟1
入棧第一個(gè)元素，因?yàn)槭堑谝粋€(gè)元素，因此最小值就是此元素的值。
操作步驟2
入棧第二個(gè)元素，如下圖所示：
因?yàn)槿霔５脑?3 比 8 小，所以先將棧中的原最小值 8 存入棧中，再將 3 入棧。
操作步驟3
入棧第三個(gè)元素，如下圖所示：
因?yàn)槿霔Ｔ?5 大于 3，因此棧中的最小值不變，直接將元素 5 入棧。
操作步驟4
繼續(xù)入棧，如下圖所示：
入棧元素 1 小于于 3，因此先將原最小值 3 入棧，再將 1 入棧，棧中的最小值更改為 1。
操作步驟5
執(zhí)行出棧操作，如下圖所示：
元素 1 出棧，判斷當(dāng)前元素就是棧的最小值，因此將棧頂元素 3 設(shè)置為最小值，并移除元素 3，如下圖所示：
操作步驟6
繼續(xù)出棧，如下圖所示：
因?yàn)樵?5 不是當(dāng)前最小值，因此直接出棧。
操作步驟7
繼續(xù)出棧，如下圖所示：
因?yàn)槌鰲Ｔ?3 為最小值，因此繼續(xù)將最小值設(shè)置為棧頂元素 8，并將棧頂元素出棧，如下圖所示：
這樣就剩下最后一個(gè)元素了，最后一個(gè)元素出棧之后就成空棧了，整個(gè)流程就執(zhí)行完了。
實(shí)現(xiàn)代碼1
接下來(lái)我們將上面的思路用代碼實(shí)現(xiàn)一下，我們用數(shù)組實(shí)現(xiàn)的棧來(lái)實(shí)現(xiàn)相關(guān)的功能，代碼如下：
class MinStack {
private int[] data; // 棧數(shù)據(jù)
private int maxSize; // 最大長(zhǎng)度
private int top; // 棧頂指針（下標(biāo)）
private int min; // 最小值
// 構(gòu)造函數(shù)
public MinStack() {
// 設(shè)置默認(rèn)值
maxSize = 10000;
data = new int[maxSize];
top = -1;
min = Integer.MAX_VALUE;
}
// 入棧（添加元素）
public void push(int x) {
if (min >= x) {
// 遇到了更小的值，記錄原最小值（入棧）
data[++top] = min;
min = x;
}
// 當(dāng)前值入棧
data[++top] = x;
}
// 出棧（移除棧頂元素）
public void pop() {
if (min == data[top]) {
min = data[--top]; // 拿到原最小值，并（將原最小值）出棧
}
--top; // 出棧
}
// 查找棧頂元素
public int top() {
return data[top];
}
// 查詢最小值
public int min() {
return min;
}
}上述代碼在 LeetCode 的執(zhí)行結(jié)果如下：
可以看出性能還是很高的，超越了 99.92% 的用戶，內(nèi)存消耗也不大。它的核心代碼在 push 方法內(nèi)，先將原最小值和最新最小值相繼入棧，在 pop 出棧時(shí)判斷出棧元素是否為最小值，如果是最小值則將當(dāng)前最小值指向棧頂元素并將棧頂元素出棧，這樣就得到了下一個(gè)新的最小值了。
實(shí)現(xiàn)代碼2
如果我們不想使用數(shù)組的自定義棧來(lái)實(shí)現(xiàn)，還可以使用 Java 中自帶的棧 Stack 來(lái)實(shí)現(xiàn)此功能，代碼如下：
class MinStack {
private Stack stack = new Stack();
private int min = Integer.MAX_VALUE;
public MinStack() { }
// 入棧（添加元素）
public void push(int x) {
if (x 這種實(shí)現(xiàn)代碼的方式（使用 Java API），在刷題或者實(shí)際面試中如果沒(méi)有特殊說(shuō)明是可以直接用的。
### 總結(jié)
本文我們通過(guò)兩種方式：自定義數(shù)組棧和 Java API 中的 `Stack` 來(lái)實(shí)現(xiàn)了棧中最小值的功能，保證了在調(diào)用棧的 min、push 及 pop 方法時(shí)的時(shí)間復(fù)雜度都是 O(1)。兩種實(shí)現(xiàn)方式的代碼雖然略不相同，但實(shí)現(xiàn)思路都是一樣的，都是**在元素入棧時(shí)判斷當(dāng)前元素是否小于最小元素，如果小于最小元素則先將原最小值入棧，再將當(dāng)前最小元素入棧，這樣當(dāng)調(diào)用 pop 方法時(shí)，即使移除的是最小值，只需要將下一個(gè)元素取出即為新的最小值了**，這樣就可以實(shí)現(xiàn)調(diào)用 min、push 及 pop 方法時(shí)的時(shí)間復(fù)雜度都是 O(1) 了。
>文章來(lái)源于公眾號(hào)：Java中文社群 作者：磊哥
以上就是`W3Cschool編程獅`關(guān)于**算法圖解：如何找出棧中的最小值？**的相關(guān)介紹了，希望對(duì)大家有所幫助。
