成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Min Stack 最小棧

YorkChen / 2057人閱讀

摘要：雙棧法復(fù)雜度時(shí)間空間思路暴力的方法是遍歷一遍棧得出最小值，這樣不用任何空間。因?yàn)檫@個(gè)最小值的順序也是先進(jìn)后出，我們同樣用一個(gè)棧來記錄。這樣主棧在時(shí)，如果該值小于等于副棧頂，就也進(jìn)副棧中。當(dāng)主棧時(shí)，如果出的元素是副棧棧頂?shù)脑?，副棧也要?/p>

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.
雙棧法 復(fù)雜度

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

思路

暴力的方法是遍歷一遍棧得出最小值，這樣不用任何空間。但如果我們能使用空間來記錄到目前為之最小的數(shù)呢？我們只要記錄一個(gè)最小數(shù)的順序，和棧的操作順序?qū)?yīng)起來就可以在任何時(shí)候做到O(1)獲取最小值了。因?yàn)檫@個(gè)最小值的順序也是先進(jìn)后出，我們同樣用一個(gè)棧來記錄。這樣主棧在push時(shí)，如果該值小于等于副棧頂，就也push進(jìn)副棧中。當(dāng)主棧pop時(shí)，如果pop出的元素是副棧棧頂?shù)脑挘睏Ｒ惨猵op。

注意

判斷是否加入副棧時(shí)，等于的情況也要加入，因?yàn)榭赡苡卸鄠€(gè)重復(fù)的最小值，我們也需要多次拋出這些重復(fù)的最小值

當(dāng)棧為空時(shí)，peek會(huì)拋出異常，這里要和面試官溝通好如何處理?xiàng)榭盏那闆r

代碼 
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
后續(xù) Follow Up

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64525.html

相關(guān)文章

  • LeetCode 155：最小棧 Min Stack

    摘要：刪除棧頂?shù)脑??？梢粤硗庑陆ㄒ粋€(gè)棧來順序存入數(shù)據(jù)最小值。另外在數(shù)據(jù)入棧時(shí)需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應(yīng)該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會(huì)溢出。 LeetCode 155：最小棧 Min Stack 設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。 push(x) -- ...

    LeexMuller 評論0 收藏0

  • 力扣(LeetCode)155

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

    Scliang 評論0 收藏0

  • [Leetcode] Verify Preorder Sequence in Binary Sear

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

    未東興 評論0 收藏0

  • LeetCode[132] Pattern

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

    go4it 評論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

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

    張漢慶 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<