LeetCode 155：最小棧 Min Stack

LeexMuller 發布于2019-08-19 10:16 / 3416人閱讀

摘要：刪除棧頂的元素。可以另外新建一個棧來順序存入數據最小值。另外在數據入棧時需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會溢出。

LeetCode 155：最小棧 Min Stack

設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。

push(x) -- 將元素 x 推入棧中。

pop() -- 刪除棧頂的元素。

top() -- 獲取棧頂元素。

getMin() -- 檢索棧中的最小元素。

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解題思路：

起初我以為定義一個指針指向最小值即可，后面才想到在棧中彈出元素時，如果彈出的元素是最小值，那這個指針就需要更改選擇另一個最小元素。沒辦法，想做到入棧出棧和彈出最小值均為 O(1) 的時間復雜度，那么只能犧牲空間來換。可以另外新建一個棧來順序存入數據最小值。

注意：Python中沒有多帶帶的 Stack 數據結構，其實它的數組就有彈出和壓入功能。也可以用 collections.deque() 數據結構。另外在數據入棧時需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會溢出。

事實上每次都要調用函數判斷是否為空這個操作，相對這道題的運行時間來說很耗時，就這道題而言是可以避免的，只需給輔助棧加入整型最大值作為棧底元素即可。

Java：

class MinStack {
    Stack s1 = new Stack<>();//初始化棧
    Stack s2 = new Stack<>();//輔助棧順序存入最小值

    public MinStack() {
        s2.push(Integer.MAX_VALUE);//先加入整型最大值在棧底，避免判斷輔助棧是否為空
    }

    public void push(int x) {
        s1.push(x);
        if (s2.peek() >= x) s2.push(x);//比棧頂元素值小或相等就加入輔助棧
    }

    public void pop() {
        int tmp = s1.pop();
        if (tmp == s2.peek()) s2.pop();//彈出棧的元素值如果和輔助棧頂元素值相等，也在輔助棧彈出它
    }

    public int top() {
        return s1.peek();//返回棧頂元素
    }

    public int getMin() {
        return s2.peek();//返回輔助棧棧頂元素即是最小值
    }
}

Python3：

class MinStack:
    #初始化數據結構(數組)，s2作為輔助棧加入整形最大值做棧底，避免判斷輔助棧是否為空
    def __init__(self):
        self.s1 = []
        self.s2 = []
        self.s2.append(sys.maxsize)

    def push(self, x: int) -> None:
        self.s1.append(x)
        #取棧頂元素直接用數組負值索引 Array[-1] 取最后一個值
        if self.s2[-1] >= x: self.s2.append(x)

    def pop(self) -> None:
        tmp = self.s1.pop()
        if tmp == self.s2[-1]: self.s2.pop()

    def top(self) -> int:
        return self.s1[-1]

    def getMin(self) -> int:
        return self.s2[-1]

云服務器 GPU云服務器 155瀏覽器 LeetCode Stack LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/75733.html

力扣(LeetCode)155

摘要：題目地址題目描述設計一個支持，，操作，并能在常數時間內檢索到最小元素的棧。將元素推入棧中。刪除棧頂的元素。示例返回返回返回解答每次入棧都放入兩個元素，分別是當前元素，和當前的最小元素因此放入之前需要和當前值進行比較。題目地址：https://leetcode-cn.com/probl...題目描述：設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。 p...

Scliang 2019-08-16 15:21 評論0 收藏0
[Leetcode] Min Stack 最小棧

摘要：雙棧法復雜度時間空間思路暴力的方法是遍歷一遍棧得出最小值，這樣不用任何空間。因為這個最小值的順序也是先進后出，我們同樣用一個棧來記錄。這樣主棧在時，如果該值小于等于副棧頂，就也進副棧中。當主棧時，如果出的元素是副棧棧頂的話，副棧也要。 Min Stack Design a stack that supports push, pop, top, and retrieving themin...

YorkChen 2019-08-14 12:31 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[Leetcode] Verify Preorder Sequence in Binary Sear

摘要：如果繼續降序，說明又向左走了，這樣等到下次向右走得時候也要再次更新最小值。這樣，序列無效的條件就是違反了這個最小值的限定。我們同樣可以用本題的方法解，不過是從數組的后面向前面遍歷，因為在后面了。棧的增長方向也是從高向低了。 Verify Preorder Sequence in Binary Search Tree Given an array of numbers, verify ...

未東興 2019-08-14 12:46 評論0 收藏0