【劍指offer】13.包含min函數的棧

yanest 發布于2019-08-23 15:10 / 2423人閱讀

摘要：題目定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的函數時間復雜度應為。這樣最小值棧的棧頂永遠是當前棧的最小值。

題目

定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））。

思路

1.定義兩個棧，一個棧用于存儲數據，另一個棧用于存儲每次數據進棧時棧的最小值.

2.每次數據進棧時，將此數據和最小值棧的棧頂元素比較，將二者比較的較小值再次存入最小值棧.

4.數據棧出棧，最小值棧也出棧。

3.這樣最小值棧的棧頂永遠是當前棧的最小值。

代碼

var dataStack = [];
var minStack = [];
 
function push(node)
{
    dataStack.push(node);
    if(minStack.length === 0 ||  node < min()){
        minStack.push(node);
    }else{
        minStack.push(min());
    }
}
function pop()
{
    minStack.pop();
    return dataStack.pop();
}
function top()
{
    var length = dataStack.length;
    return length>0&&dataStack[length-1]
}
function min()
{
    var length = minStack.length;
    return length>0&&minStack[length-1]
}

GPU云服務器云服務器包含文件函數劍指 java的棧使用 offer

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

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

【劍指offer】讓抽象問題具體化

摘要：假設壓入棧的所有數字均不相等。注意這兩個序列的長度是相等的思路借助一個輔助棧來存儲數據。當所有數據入棧完成，如果出棧順序正確，那么輔助棧應該為空。若存在，左右子樹，遞歸檢測左右子樹是否復合規范。 1.包含min函數的棧定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））。思路 1.定義兩個棧，一個棧用于存儲數據，另一個棧用于存儲每次數...

Keagan 2019-08-23 15:15 評論0 收藏0
劍指offer--JavaScript版

摘要：劍指在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。其中負數用補碼表示。本文為8月牛客網《劍指 offer》刷題做得，現整理出來作為參考。雖然是算法題，但本文用 JavaScript 編寫，看了《劍指 offer》以后發現很多問題處理的過程并不是最好的，所以本文僅供參考。以前全部代碼 A...

MarvinZhang 2019-08-23 11:52 評論0 收藏0
【劍指offer】8.斐波那契數列

摘要：題目題目描述大家都知道斐波那契數列，現在要求輸入一個整數，請你輸出斐波那契數列的第項從開始，第項為。基本思路這道題在劍指中實際是當作遞歸的反例來說的。明顯也符合斐波那契數列的規律矩形覆蓋我們可以用的小矩形橫著或者豎著去覆蓋更大的矩形。題目題目描述大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。基本思路這道題在劍指offer中...

sf_wangchong 2019-08-23 14:50 評論0 收藏0
劍指offer/LintCode12_最小棧

摘要：劍指最小棧聲明文章均為本人技術筆記，轉載請注明出處解題思路實現功能實現一個最小棧，要求操作均為復雜度，解題思路用棧存儲數據用最小棧存儲中最小元素，保證棧頂元素與棧頂元素同步，表示此時最小值將與此時最小值比較，將更小的一方壓棧，保證中棧頂始終劍指offer/LintCode12_最小棧聲明文章均為本人技術筆記，轉載請注明出處https://segmentfault.com/u/yz...

Betta 2019-08-14 18:12 評論0 收藏0
劍指offer(javascript版)

摘要：二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。 1.二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數...

imtianx 2019-08-20 15:20 評論0 收藏0