劍指 Offer 31. 棧的壓入、彈出序列

輸入兩個(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} 就不可能是該壓棧序列的彈出序列。

?

示例 1：

輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

輸出：true

解釋?zhuān)何覀兛梢园匆韵马樞驁?zhí)行：

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

輸出：false

解釋?zhuān)? 不能在 2 之前彈出。

這道題主要是運(yùn)用輔助棧，i來(lái)指示pop表中的數(shù)字，如果pop表中的數(shù)字和輔助棧當(dāng)前指向的數(shù)字相同，說(shuō)明應(yīng)該彈出，并且pop表要指向下一個(gè)數(shù)字。

如果最后輔助棧能夠?yàn)榭?，說(shuō)明可以完全彈出，則是彈出序列。

class?Solution:

????def?validateStackSequences(self,?pushed:?List[int],?popped:?List[int])?->?bool:

????????supStack=[]

????????i=0

????????for?num?in?pushed:

????????????supStack.append(num)

????????????while?supStack?and?supStack[-1]==popped[i]:

????????????????supStack.pop()

????????????????i+=1

????????return?not?supStack