【刷算法】包含min函數的棧

justCoding 發布于2019-08-22 18:21 / 2903人閱讀

摘要：題目描述定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的函數。

題目描述

定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。

分析

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

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

代碼實現

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云服務器云服務器包含文件函數 java的棧使用最新函數與算法 min

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

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

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

摘要：題目定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的函數時間復雜度應為。這樣最小值棧的棧頂永遠是當前棧的最小值。題目定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間復雜度應為O（1））。思路 1.定義兩個棧，一個棧用于存儲數據，另一個棧用于存儲每次數據進棧時棧的最小值. 2.每次數據進棧時，將此數據和最小值棧的棧頂元素比較，將二者比...

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

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

wing324 2019-08-23 11:31 評論0 收藏0
電機控制及調參

摘要：有刷電機結構簡單開發久技術成熟響應速度快，起動扭矩大運行平穩，起制動效果好控制精度高使用成本低，維修方便而無刷電機由于無電刷，具有低干擾噪音低運轉順暢壽命長低維護成本等優點。電機控制方式力矩控制指定電機提供設置大小的力矩。 ...

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

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

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

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

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