找出棧中最小值的方法是什么

本篇內(nèi)容介紹了“找出棧中最小值的方法是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

題目

定義棧的數(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/

思考

首先來說這道題目本身很好理解，它的實(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)。

也就是說，在我們執(zhí)行了 pop 時(shí)如果移除的棧中最小的值，那么如何尋找棧中的下一個(gè)最小元素?并且要保證操作的時(shí)間復(fù)雜度為  O(1)。這個(gè)時(shí)間復(fù)雜度制約了我們在移除了最小值之后不能通過遍歷查找下一個(gè)最小值，所以這就成為了這道題的難點(diǎn)。

比如當(dāng)我們移除以下棧頂元素值：

因?yàn)樽钚≈稻褪?1，因此在移除之后最小值也被移除了，如下圖所示：

那么接下來，讓我們一起思考 3 分鐘，想一想應(yīng)該如何處理這個(gè)問題~

解題思路

其實(shí)我們可以在每次入棧時(shí)，判斷當(dāng)前元素是否小于最小值，如果小于則將原最小值和最新的最小值相繼入棧，這樣在調(diào)用 pop  時(shí)即使移除的是最小值，我們也能通過獲取下一個(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

接下來我們將上面的思路用代碼實(shí)現(xiàn)一下，我們用數(shù)組實(shí)現(xiàn)的棧來實(shí)現(xiàn)相關(guān)的功能，代碼如下：

class MinStack {     private int[] data; // 棧數(shù)據(jù)     private int maxSize; // 最大長度     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ù)組的自定義棧來實(shí)現(xiàn)，還可以使用 Java 中自帶的棧 Stack 來實(shí)現(xiàn)此功能，代碼如下：

class MinStack { private Stackstack = new Stack<>(); private  int min = Integer.MAX_VALUE; public MinStack() { } // 入棧(添加元素) public void  push(int x) { if (x <= min) { // 遇到了更小的值，記錄原最小值(入棧) stack.push(min); min = x;  } stack.push(x); } // 出棧(移除棧頂元素) public void pop() { if (stack.pop() == min) {  min = stack.pop(); // 取出原最小值 } } // 查找棧頂元素 public int top() { return  stack.peek(); } // 查詢最小值 public int min() { return min; }}

上述代碼在 LeetCode 的執(zhí)行結(jié)果如下：

從結(jié)果可以看出，使用 Java 中自帶的棧的性能不如自定義數(shù)組的棧，但代碼還是通過了測試。這種實(shí)現(xiàn)方式的優(yōu)點(diǎn)就是代碼比較簡單，可以利用了 Java 自身的  API 來完成了最小值的查找。

這種實(shí)現(xiàn)代碼的方式(使用 Java API)，在刷題或者實(shí)際面試中如果沒有特殊說明是可以直接用的。

“找出棧中最小值的方法是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！