題目描述

輸入兩個(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í)點(diǎn)

棧

Qiang的思路

對(duì)于一個(gè)棧，當(dāng)壓入序列確定時(shí)，當(dāng)給出第一個(gè)彈出元素，就會(huì)將壓入序列分成兩段，對(duì)于前半段的元素必須先彈出后面的，因?yàn)榇藭r(shí)前半段全被壓入棧中，但是后半段元素可以任意彈出，因?yàn)楹蟀攵蔚膲喝肭闆r不確定。然后對(duì)于第二個(gè)彈出元素時(shí)，我們需要從上一時(shí)刻的位置往后遍歷，如果遇到相同的那就是這個(gè)元素彈出了 ，如果沒(méi)有那么需要往前遍歷。在往前遍歷時(shí)，如果遇到的第一個(gè)未彈出元素和當(dāng)前彈出元素相等，那么就是這個(gè)元素需要彈出，如果不相等那么這個(gè)彈出序列并不是壓入序列的彈出序列。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        if len(popV)==0:
            return True
        pos=-1
        for j in range(len(popV)):
            flag=False
            for i in range(pos+1, len(popV)):
                if pushV[i]==popV[j]:
                    pushV[i]=None
                    pos=i
                    flag=True
                    break
            if flag==True:
                continue
            for i in range(pos-1,-1,-1):
                if pushV[i]==popV[j]:
                    pushV[i]=None
                    pos=i
                    flag=True
                    break
                if pushV[i]!=None:
                    return False
            if flag==False:
                return False
        return True

首先需要從上一時(shí)刻找到彈出元素的位置出發(fā)，往后找，如果找到了彈出元素，則記錄該位置，并開(kāi)始下一輪尋找。如果沒(méi)有找到，那么需要往前找，但是往前找的時(shí)候不用考慮之前彈出的元素，只需要關(guān)注第一個(gè)未被彈出的元素，如果他和當(dāng)前彈出的元素相等則繼續(xù)下一輪尋找，如果不相等則說(shuō)明不是彈出序列。

同時(shí)，需要注意，可能當(dāng)前彈出元素都不在壓入序列中，所以如果查找了一遍并沒(méi)有發(fā)現(xiàn)彈出元素，那么我們可以提前終止遍歷，彈出序列一定不是壓入序列的彈出結(jié)果。

Book中的思路

書(shū)中引入了輔助棧的概念，增加是空間復(fù)雜度，但是不需要往前遍歷，只需要看棧頂元素即可，但是往后遍歷還是需要的，所以在一定的程度上降低了時(shí)間復(fù)雜度。

# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        s=[]
        while popV!=[]:
            c=popV.pop(0)
            if s!=[] and s[-1]==c:
                s.pop(-1)
                continue
            flag=False
            while pushV!=[]:
                _c=pushV.pop(0)
                if c==_c:
                    flag=True
                    break
                s.append(_c)
            if flag==False:
                return False
        return True

每次需要先查看輔助棧的棧頂元素，如果棧頂元素等于當(dāng)前的彈出元素，那么就找到了彈出元素，如果并不相等，則需要將其他的壓入元素壓入到棧中，同時(shí)比較是不是和當(dāng)前彈出元素相等，如果遇到一個(gè)相等的元素那么便可以結(jié)束壓入過(guò)程，該元素就是彈出元素，如果將所有的元素都?jí)喝肓藯Ｖ羞€是沒(méi)有找到，這說(shuō)明彈出序列并不是壓入序列的彈出序列。

作者原創(chuàng)，如需轉(zhuǎn)載及其他問(wèn)題請(qǐng)郵箱聯(lián)系：lwqiang_chn@163.com。
個(gè)人網(wǎng)站：https://www.myqiang.top。