Python程式檢查給定的入棧出棧序列是否正確

假設我們有一個名為pushes的數字列表，以及另一個名為pops的數字列表，我們需要檢查這是否是一個有效的棧推入和彈出操作序列。

因此，如果輸入類似於pushes = [1, 2, 5, 7, 9] pops = [2, 1, 9, 7, 5]，則輸出將為True，因為我們可以先推入[1, 2]，然後將它們都彈出。然後推入[5, 7, 9]並全部彈出。

為了解決這個問題，我們將遵循以下步驟：

• s := 一個新的棧
• i := 0
• 對於pushes中的每個元素ele，執行以下操作：
  • 將ele推入s
  • 當s的大小 > 0 且 pops[i] 與s的棧頂元素相同，執行以下操作：
    • 從s中刪除棧頂元素
    • i := i + 1
• 當s的大小為0時返回true，否則返回false

讓我們看看下面的實現以獲得更好的理解：

示例

線上演示

class Solution:
   def solve(self, pushes, pops):
      s = []
      i = 0

      for ele in pushes:
         s.append(ele)

         while len(s) > 0 and pops[i] == s[-1]:
            s.pop()
            i += 1

      return len(s) == 0

ob = Solution()
pushes = [1, 2, 5, 7, 9]
pops = [2, 1, 9, 7, 5]
print(ob.solve(pushes, pops))

輸入

[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]

輸出

True

Arnab Chakraborty

更新於: 2020-12-02

188 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習