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

更新于: 2020-12-02

188 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告