【刷算法】包含min函數(shù)的棧

justCoding 發(fā)布于2019-08-22 18:21 / 2908人閱讀

摘要：題目描述定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的函數(shù)。

題目描述

定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)。

分析

該題目要求實現(xiàn)一個帶有返回當(dāng)前棧中最小元素功能的數(shù)據(jù)結(jié)構(gòu)，首先會想到使用一個變量保存當(dāng)前最小元素的下標(biāo)，但是仔細(xì)一想，如果當(dāng)前最小元素剛好在棧頂，此時執(zhí)行pop操作，那么最小元素會被彈出，新的最小元素又上哪兒找呢？比較暴力的方法是出現(xiàn)這種情況時，再遍歷一遍棧就能重新得到最小元素的下標(biāo)，但是這么暴力操作就沒意思了而且時間復(fù)雜度很好。

可以使用雙棧來實現(xiàn)min功能，棧1常規(guī)保存元素，棧2保存此時此刻的棧中最小元素，比如說有元素進(jìn)棧1，如果該元素小于棧2的棧頂元素，說明新的最小元素就是該進(jìn)棧元素，否則，最小元素還是棧2的棧頂元素。

代碼實現(xiàn)

var stack1 = [];
var stack2 = [];

function push(node)
{
    if(stack2.length === 0 && stack1.length === 0){
        stack1.push(node);
        stack2.push(node);
    } else{
        stack1.push(node);
        var stack2Top = stack2[stack2.length-1];
        if(node < stack2Top)
            stack2.push(node)
        else
            stack2.push(stack2Top);
    }
    
}
function pop()
{
    stack2.pop();
    return stack1.pop();
}
function top()
{
    return stack1[stack1.length-1];
}
function min()
{
    return stack2[stack2.length-1];
}

GPU云服務(wù)器云服務(wù)器包含文件函數(shù) java的棧使用最新函數(shù)與算法 min

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

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

相關(guān)文章

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

摘要：題目定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的函數(shù)時間復(fù)雜度應(yīng)為。這樣最小值棧的棧頂永遠(yuǎn)是當(dāng)前棧的最小值。題目定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復(fù)雜度應(yīng)為O（1））。思路 1.定義兩個棧，一個棧用于存儲數(shù)據(jù)，另一個棧用于存儲每次數(shù)據(jù)進(jìn)棧時棧的最小值. 2.每次數(shù)據(jù)進(jìn)棧時，將此數(shù)據(jù)和最小值棧的棧頂元素比較，將二者比...

yanest 2019-08-23 15:10 評論0 收藏0
【刷算法】LeetCode.155-最小棧

摘要：題目描述設(shè)計一個支持，，操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。刪除棧頂?shù)脑亍z索棧中的最小元素。示例返回返回返回代碼實現(xiàn) 題目描述設(shè)計一個支持 push，pop，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。 push(x) -- 將元素 x 推入棧中。 pop() -- 刪除棧頂?shù)脑亍?top() -- 獲取棧頂元素。 getMin() -- 檢索棧中的最小元素。示例...

wing324 2019-08-23 11:31 評論0 收藏0
電機(jī)控制及調(diào)參

摘要：有刷電機(jī)結(jié)構(gòu)簡單開發(fā)久技術(shù)成熟響應(yīng)速度快，起動扭矩大運(yùn)行平穩(wěn)，起制動效果好控制精度高使用成本低，維修方便而無刷電機(jī)由于無電刷，具有低干擾噪音低運(yùn)轉(zhuǎn)順暢壽命長低維護(hù)成本等優(yōu)點(diǎn)。電機(jī)控制方式力矩控制指定電機(jī)提供設(shè)置大小的力矩。 ...

不知名網(wǎng)友 2021-11-26 11:10 評論0 收藏0
?算法入門?《二叉樹 - 二叉搜索樹》簡單05 —— LeetCode 897. 遞增順序搜索樹

文章目錄一、題目1、題目描述2、基礎(chǔ)框架3、原題鏈接二、解題報告1、思路分析2、時間復(fù)雜度3、代碼詳解三、本題小知識四、加群須知一、題目 1、題目描述 ??給你一棵二叉搜索樹，請按中序遍歷將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節(jié)點(diǎn)成為樹的根節(jié)點(diǎn)，并且每個節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，只有一個右子節(jié)點(diǎn)。??樣例輸入： [5,3,6,2,4,null,8,1,null,null,nu...

Soarkey 2021-09-10 10:51 評論0 收藏0
＜LeetCode天梯＞Day031 驗證二叉搜索樹（遞歸+中序遍歷） | 初級算法 | Pytho

摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 評論0 收藏0