min stack

yy13818512006 發布于2019-08-16 10:33 / 769人閱讀

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();
    }
}

GPU云服務器云服務器 Stacking Stacked Stacks Stack

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

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

[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 評論0 收藏0
每周一練之數據結構與算法（Stack）

摘要：二實現一個棧，并實現下面方法添加一個新元素到棧頂。移除棧頂的元素，同時返回被移除的元素。十進制轉換為二進制請輸入正確的數值方法簡單實現下面這個方法，其實不太好，因為沒有怎么用到這次要練習的棧方法，哈哈。最近公司內部在開始做前端技術的技術分享，每周一個主題的每周一練，以基礎知識為主，感覺挺棒的，跟著團隊的大佬們學習和復習一些知識，新人也可以多學習一些知識，也把團隊內部學習氛圍營造起來...

hzx 2019-08-23 16:55 評論0 收藏0
【刷算法】包含min函數的棧

摘要：題目描述定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的函數。題目描述定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。分析該題目要求實現一個帶有返回當前棧中最小元素功能的數據結構，首先會想到使用一個變量保存當前最小元素的下標，但是仔細一想，如果當前最小元素剛好在棧頂，此時執行pop操作，那么最小元素會被彈出，新的最小元素又上哪兒找呢？比較暴力的方...

justCoding 2019-08-22 18:21 評論0 收藏0
我的面試準備過程--隊列與棧(更新中)

摘要：和三個方法的時間復雜度必須為兩種解法，解法一，將最小值存入自有的數據結構中，如下所示原本的值最小值解法二，用兩個棧堆棧和隊列統稱線性表簡單的線性結構數組和鏈表可以實現這兩種數據結構堆棧基本理解 DFS 深度優先---按深度遍歷遞歸轉非遞歸隊列基本理解 BFS 廣度優先---按層序遍歷出入棧的合法性模擬出入棧的過程，不是入棧，就是...

EastWoodYang 2019-08-16 10:38 評論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