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

示例

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

• 輸出：true

• 解釋：我們可以按以下順序執(zhí)行：

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

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

提示

• 0 ≤ pushed.length == popped.length ≤ 1000

• 0 ≤ pushed[i], popped[i] ＜ 1000

• pushed 是 popped 的排列。

方法：輔助棧

按照 壓入順序的序列 依次壓入 1、2、3、4、5，每把一個(gè)元素壓入到棧中的時(shí)候都 “把棧頂元素和彈出順序的序列進(jìn)行比對(duì)”，發(fā)現(xiàn) 4 是彈出順序的序列的第一個(gè)值，即按照規(guī)則把 4 彈出。

現(xiàn)在輔助棧中只有 1、2、3，彈出順序的序列指針指向的是 5，繼續(xù)壓入 5 ，此時(shí)輔助棧是1、2、3、5，發(fā)現(xiàn)棧頂元素與彈出順序的序列的第一個(gè)值一致，彈出 5 ；以此類推，直至輔助隊(duì)列為空，說(shuō)明假設(shè)成立。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度： O(N) ，其中 N 是 pushed 序列的長(zhǎng)度。

• 空間復(fù)雜度： O(N)。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。