【刷算法】棧的壓入、彈出序列

CarlBenjamin 發(fā)布于2019-08-22 18:17 / 1404人閱讀

摘要：題目描述輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。

題目描述

輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個(gè)序列的長(zhǎng)度是相等的）

分析

其實(shí)該題就是考察一個(gè)進(jìn)棧序列能否和一個(gè)出棧序列對(duì)應(yīng)起來(lái)，但是棘手的地方在于：一個(gè)進(jìn)棧序列可能會(huì)有多個(gè)出棧的順序，所以還是得好好想一想。

可以從一個(gè)簡(jiǎn)單的例子開始：

序列A：1,2,3

序列B：2,3,1

1先進(jìn)棧，B序列中未出棧的第一個(gè)數(shù)字是2，說(shuō)明此時(shí)1不能再接著出棧；

2再進(jìn)棧，B序列中未出棧的第一個(gè)數(shù)字是2，說(shuō)明第一個(gè)出棧的數(shù)字是2，那么2就此出棧；

此時(shí)棧頂元素為1，B序列中未出棧的第一個(gè)數(shù)字是1，說(shuō)明1是自2出棧后的再一個(gè)出棧元素，那么1就此出棧，此時(shí)棧為空；

3繼續(xù)進(jìn)棧，此時(shí)B序列的中未出棧的第一個(gè)數(shù)字是3，說(shuō)明3是再一個(gè)出棧元素，那么3就此出棧，此時(shí)棧為空，序列A也全都進(jìn)棧完畢了；

?？樟?，序列A也進(jìn)棧完畢了，說(shuō)明B就是A的彈出序列。

代碼實(shí)現(xiàn)

接著這個(gè)思路，可以試著寫代碼了

function IsPopOrder(pushV, popV)
{
    if(pushV.length === 0 || popV.length === 0 || pushV.length !== popV.length)
        return false;
    // 進(jìn)棧序列和出棧序列分別有一個(gè)指針，從頭開始
    var curPushIndex = 0, curPopIndex = 0;
    var stack = [];
    
    for(;curPushIndex < pushV.length;curPushIndex++) {
        
        stack.push(pushV[curPushIndex]);
        while(curPopIndex < popV.length && stack[stack.length-1] === popV[curPopIndex]){
        // 棧頂元素和當(dāng)前popIndex指向的數(shù)字一樣的話，stack彈出棧頂元素，且當(dāng)前popIndex指向pop序列的下一個(gè)數(shù)字
            stack.pop();
            curPopIndex++;
        }
    }
    // 棧中元素沒(méi)有全部彈出，說(shuō)明兩個(gè)序列并不匹配，否則，就是匹配
    return stack.length === 0;
}

GPU云服務(wù)器云服務(wù)器最大功序列算法 php 壓入 web服務(wù)器的壓測(cè) 全棧的

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/95697.html

相關(guān)文章

劍指offer：棧的壓入、彈出序列（Java）

摘要：題目描述輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序。指向壓棧序列的指針指向彈棧序列的指針儲(chǔ)存壓棧序列的輔助空間第一次遍歷把壓棧序列放入輔助空間中如果有相等的就讓彈棧序列指針。 1.題目描述輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序，請(qǐng)判斷第二個(gè)序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓...

Zhuxy 2019-08-19 10:11 評(píng)論0 收藏0
【劍指offer】讓抽象問(wèn)題具體化

摘要：假設(shè)壓入棧的所有數(shù)字均不相等。注意這兩個(gè)序列的長(zhǎng)度是相等的思路借助一個(gè)輔助棧來(lái)存儲(chǔ)數(shù)據(jù)。當(dāng)所有數(shù)據(jù)入棧完成，如果出棧順序正確，那么輔助棧應(yīng)該為空。若存在，左右子樹，遞歸檢測(cè)左右子樹是否復(fù)合規(guī)范。 1.包含min函數(shù)的棧定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?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
Java數(shù)據(jù)結(jié)構(gòu)與算法[原創(chuàng)]——棧

摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。方法調(diào)用編寫的程序在進(jìn)行方法函數(shù)調(diào)用時(shí)，會(huì)完成對(duì)方法的壓棧操作，等方法執(zhí)行結(jié)束后，對(duì)應(yīng)的會(huì)完成對(duì)方法的彈棧操作。聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)中的棧的概念、存儲(chǔ)結(jié)構(gòu)、棧的特點(diǎn)以及棧的適用場(chǎng)景，另外會(huì)穿插介紹面試中的一些經(jīng)典問(wèn)題...

hiyang 2019-08-19 10:42 評(píng)論0 收藏0
棧的實(shí)現(xiàn)原理

摘要：使用棧實(shí)現(xiàn)字符串逆序?qū)⒆址崔D(zhuǎn)用兩個(gè)棧實(shí)現(xiàn)隊(duì)列用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的和操作。假設(shè)棧中有個(gè)元素，基于簡(jiǎn)單數(shù)組實(shí)現(xiàn)的棧?？梢钥吹綏Ｊ菍?shí)現(xiàn)，其實(shí)底層也是用數(shù)組來(lái)實(shí)現(xiàn)的。移除此堆棧頂部的對(duì)象，并將該對(duì)象作為此函數(shù)的值返回。目錄介紹 01.棧由簡(jiǎn)單數(shù)據(jù)實(shí)現(xiàn) 1.1 簡(jiǎn)單數(shù)組代碼實(shí)現(xiàn) 1.2 可能出現(xiàn)問(wèn)題 1.3 性能和局限性 02.棧由動(dòng)態(tài)數(shù)組實(shí)現(xiàn) 2.1 基于簡(jiǎn)單...

soasme 2019-08-19 11:35 評(píng)論0 收藏0
2019秋招知識(shí)盲點(diǎn)總結(jié)

摘要：實(shí)際上是一個(gè)讓出線程的標(biāo)志遇到會(huì)立即返回一個(gè)狀態(tài)的。一個(gè)簡(jiǎn)單的防抖函數(shù)如果定時(shí)器存在則清除重新開始定時(shí)執(zhí)行缺點(diǎn)只能在最后執(zhí)行，不能立即被執(zhí)行，在某些情況下不適用。假設(shè)壓入棧的所有數(shù)字均不相等。接收數(shù)據(jù)不受同源政策限制。開始盡管秋招還沒(méi)有拿到offer（好難過(guò)），但是一些知識(shí)點(diǎn)還是要總結(jié)的，既然自己選了這條路，那就一定要堅(jiān)定不移的走下去...... 注意 new 運(yùn)算符的優(yōu)先級(jí) fu...

Doyle 2019-08-23 11:52 評(píng)論0 收藏0