[Leetcode] Min Stack 最小棧

YorkChen 發布于2019-08-14 12:31 / 2052人閱讀

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

Min Stack

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.

雙棧法 復雜度

時間 O(N) 空間 O(1)

思路

暴力的方法是遍歷一遍棧得出最小值，這樣不用任何空間。但如果我們能使用空間來記錄到目前為之最小的數呢？我們只要記錄一個最小數的順序，和棧的操作順序對應起來就可以在任何時候做到O(1)獲取最小值了。因為這個最小值的順序也是先進后出，我們同樣用一個棧來記錄。這樣主棧在push時，如果該值小于等于副棧頂，就也push進副棧中。當主棧pop時，如果pop出的元素是副棧棧頂的話，副棧也要pop。

注意

判斷是否加入副棧時，等于的情況也要加入，因為可能有多個重復的最小值，我們也需要多次拋出這些重復的最小值

當棧為空時，peek會拋出異常，這里要和面試官溝通好如何處理棧為空的情況

代碼

class MinStack {
    
    Stack stk = new Stack();
    Stack min = new Stack();
    
    public void push(int x) {
        stk.push(x);
        if(min.isEmpty() || x <= min.peek()){
            min.push(x);
        }
    }

    public void pop() {
        int x = stk.pop();
        if(!min.isEmpty() && min.peek() == x){
            min.pop();
        }
    }

    public int top() {
        if(!stk.isEmpty()){
            return stk.peek();
        } else {
            return 0;
        }
    }

    public int getMin() {
        if(!min.isEmpty()){
           return min.peek();
        } else {
            return 0;
        }
    }
}

2018/2

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.mins = []
        self.values = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.values.append(x)
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)
        

    def pop(self):
        """
        :rtype: void
        """
        result = self.values.pop() if self.values else None
        if result is not None and self.mins and result == self.mins[-1]:
            self.mins.pop()
        

    def top(self):
        """
        :rtype: int
        """
        return self.values[-1] if self.values else None

        

    def getMin(self):
        """
        :rtype: int
        """
        return self.mins[-1] if self.mins else None

后續 Follow Up

Q：如果還要加一個getMax()方法呢？
A：同樣用一個棧，但是入棧的判斷條件是大于等于棧頂。

GPU云服務器云服務器 LeetCode Stack LeetCode_String leetcode_35_SearchIn

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

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

LeetCode 155：最小棧 Min Stack

摘要：刪除棧頂的元素。可以另外新建一個棧來順序存入數據最小值。另外在數據入棧時需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會溢出。 LeetCode 155：最小棧 Min Stack 設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。 push(x) -- ...

LeexMuller 2019-08-19 10:16 評論0 收藏0
力扣(LeetCode)155

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

Scliang 2019-08-16 15:21 評論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
LeetCode[132] Pattern

摘要：復雜度思路維護一個里面有最大值和最小值。如果當前值小于的最小值，那么就將原來的壓進去棧，然后在用這個新的的值再進行更新。如果沒有適合返回的值，就重新更新當前的。 Leetcode[132] Pattern Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak ...

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

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

張漢慶 2019-08-23 13:42 評論0 收藏0