min stack

yy13818512006 發(fā)布于2019-08-16 10:33 / 825人閱讀

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

public class MinStack {
    Stack stk;
    int min;
    
    /** initialize your data structure here. */
    public MinStack() {
        stk = new Stack();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        if(x <= min){
            stk.push(min);
            min = x;
        }
        stk.push(x);
    }
    
    public void pop() {
        if(stk.peek() == min){
            stk.pop();
            min = stk.pop();
        } else {
            stk.pop();
        }
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return min;
    }
}

public class MinStack {
    ArrayDeque stack, min;
    
    public MinStack() {
        this.stack = new ArrayDeque();
        this.min = new ArrayDeque();
    }
    
    public void push(int x) {
        stack.push(x);
        if(min.isEmpty() || x <= min.peek()){
            min.push(x);
        }
    }
    
    public void pop() {
        if(stack.isEmpty()){
            return; 
        }
        if(min.peek().equals(stack.peek())){
            min.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

云服務(wù)器 GPU云服務(wù)器 Stacking Stacked Stacks Stack

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/69993.html

相關(guān)文章

[LintCode/LeetCode] Min Stack/Max Stack

Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...

GHOST_349178 2019-08-14 15:14 評(píng)論0 收藏0
每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Stack）

摘要：二實(shí)現(xiàn)一個(gè)棧，并實(shí)現(xiàn)下面方法添加一個(gè)新元素到棧頂。移除棧頂?shù)脑?，同時(shí)返回被移除的元素。十進(jìn)制轉(zhuǎn)換為二進(jìn)制請(qǐng)輸入正確的數(shù)值方法簡(jiǎn)單實(shí)現(xiàn)下面這個(gè)方法，其實(shí)不太好，因?yàn)闆]有怎么用到這次要練習(xí)的棧方法，哈哈。最近公司內(nèi)部在開始做前端技術(shù)的技術(shù)分享，每周一個(gè)主題的每周一練，以基礎(chǔ)知識(shí)為主，感覺挺棒的，跟著團(tuán)隊(duì)的大佬們學(xué)習(xí)和復(fù)習(xí)一些知識(shí)，新人也可以多學(xué)習(xí)一些知識(shí)，也把團(tuán)隊(duì)內(nèi)部學(xué)習(xí)氛圍營(yíng)造起來...

hzx 2019-08-23 16:55 評(píng)論0 收藏0
【刷算法】包含min函數(shù)的棧

摘要：題目描述定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的函數(shù)。題目描述定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。分析該題目要求實(shí)現(xiàn)一個(gè)帶有返回當(dāng)前棧中最小元素功能的數(shù)據(jù)結(jié)構(gòu)，首先會(huì)想到使用一個(gè)變量保存當(dāng)前最小元素的下標(biāo)，但是仔細(xì)一想，如果當(dāng)前最小元素剛好在棧頂，此時(shí)執(zhí)行pop操作，那么最小元素會(huì)被彈出，新的最小元素又上哪兒找呢？比較暴力的方...

justCoding 2019-08-22 18:21 評(píng)論0 收藏0
我的面試準(zhǔn)備過程--隊(duì)列與棧(更新中)

摘要：和三個(gè)方法的時(shí)間復(fù)雜度必須為兩種解法，解法一，將最小值存入自有的數(shù)據(jù)結(jié)構(gòu)中，如下所示原本的值最小值解法二，用兩個(gè)棧堆棧和隊(duì)列統(tǒng)稱線性表簡(jiǎn)單的線性結(jié)構(gòu) 數(shù)組和鏈表可以實(shí)現(xiàn)這兩種數(shù)據(jù)結(jié)構(gòu) 堆棧基本理解 DFS 深度優(yōu)先---按深度遍歷遞歸轉(zhuǎn)非遞歸隊(duì)列基本理解 BFS 廣度優(yōu)先---按層序遍歷出入棧的合法性模擬出入棧的過程，不是入棧，就是...

EastWoodYang 2019-08-16 10:38 評(píng)論0 收藏0
[Leetcode] Min Stack 最小棧

摘要：雙棧法復(fù)雜度時(shí)間空間思路暴力的方法是遍歷一遍棧得出最小值，這樣不用任何空間。因?yàn)檫@個(gè)最小值的順序也是先進(jìn)后出，我們同樣用一個(gè)棧來記錄。這樣主棧在時(shí)，如果該值小于等于副棧頂，就也進(jìn)副棧中。當(dāng)主棧時(shí)，如果出的元素是副棧棧頂?shù)脑挘睏Ｒ惨? Min Stack Design a stack that supports push, pop, top, and retrieving themin...

YorkChen 2019-08-14 12:31 評(píng)論0 收藏0