【劍指offer】13.包含min函數(shù)的棧

yanest 發(fā)布于2019-08-23 15:10 / 2417人閱讀

摘要：題目定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的函數(shù)時(shí)間復(fù)雜度應(yīng)為。這樣最小值棧的棧頂永遠(yuǎn)是當(dāng)前棧的最小值。

題目

定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））。

思路

1.定義兩個(gè)棧，一個(gè)棧用于存儲(chǔ)數(shù)據(jù)，另一個(gè)棧用于存儲(chǔ)每次數(shù)據(jù)進(jìn)棧時(shí)棧的最小值.

2.每次數(shù)據(jù)進(jìn)棧時(shí)，將此數(shù)據(jù)和最小值棧的棧頂元素比較，將二者比較的較小值再次存入最小值棧.

4.數(shù)據(jù)棧出棧，最小值棧也出棧。

3.這樣最小值棧的棧頂永遠(yuǎn)是當(dāng)前棧的最小值。

代碼

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]
}

云服務(wù)器 GPU云服務(wù)器包含文件函數(shù) 劍指 java的棧使用 offer

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/101630.html

相關(guān)文章

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

摘要：假設(shè)壓入棧的所有數(shù)字均不相等。注意這兩個(gè)序列的長度是相等的思路借助一個(gè)輔助棧來存儲(chǔ)數(shù)據(jù)。當(dāng)所有數(shù)據(jù)入棧完成，如果出棧順序正確，那么輔助棧應(yīng)該為空。若存在，左右子樹，遞歸檢測左右子樹是否復(fù)合規(guī)范。 1.包含min函數(shù)的棧定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））。思路 1.定義兩個(gè)棧，一個(gè)棧用于存儲(chǔ)數(shù)據(jù)，另一個(gè)棧用于存儲(chǔ)每次數(shù)...

Keagan 2019-08-23 15:15 評(píng)論0 收藏0
劍指offer--JavaScript版

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

MarvinZhang 2019-08-23 11:52 評(píng)論0 收藏0
【劍指offer】8.斐波那契數(shù)列

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

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

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

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

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

imtianx 2019-08-20 15:20 評(píng)論0 收藏0