｜ 棧的壓入和彈出序列

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序， 請判斷第二個序列是否為該棧的彈出順序。 假設壓入棧的所有數(shù)字均不相等。 例如，序列 {1,2,3,4,5} 是某棧的壓棧序列，序列 {4,5,3,2,1} 是該壓棧序列對應的一個彈出序列， 但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列。示例 1：輸入：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 示例 2：輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 輸出：false 解釋：1 不能在 2 之前彈出。

| 題解

class Solution:"""解題思路:1.p指針執(zhí)行pushed，q指針指向poped的第一個元素2.同時遍歷pushed 和 popped3.判斷p指針元素是否跟q指針元素相同1.如果不等 p指針后移一個單位，直到相等為止1.如果一直不等，返回false2.如果行等，讓行等的兩個元素出棧2.如果相等 讓相等的兩個元素出棧4.出棧后，p指針指向前一個元素 1.繼續(xù)判斷p和q是否相等1.如果相等 繼續(xù)出棧2.如果不等繼續(xù) p指針繼續(xù)后移5.知道遍歷結束1.判斷pushed和popped 是否為看空1.如果為空 返回True2.如果不為空 返回False"""def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:length = len(pushed)p, q = 0, 0while length > p and length > q:if popped[q] == pushed[p]: pushed.pop(p)popped.pop(q)# 特殊情況處理，第一個元素都相等的情況下，# 因為元素已經(jīng)被移除，所以重置為0即第一元素p = p - 1 if p > 0 else 0else:p += 1# 從新計算length的長度length = len(pushed)if length == 0:breakreturn False if pushed and popped else True

總結

以上是生活随笔為你收集整理的python 栈的压入弹出序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。