(栈队列堆) 剑指 Offer 31. 栈的压入、弹出序列 ——【Leetcode每日一题】

**剑指 Offer31. 栈的压入、弹出序列**

**问题描述**

给定一个整数序列，请判断该序列是否为栈的压入、弹出序列。假设每次压入或弹出的操作都是推送到栈顶，或者从栈顶弹出。

**示例1**

输入：`[2,1,3]`
输出：`true`

**示例2**

输入：`[4,5,3,24,12,2]`
输出：`false`

**示例3**

输入：`[5,4,3,2,1]`
输出：`true`

**示例4**

输入：`[1,2,3,4,5]`
输出：`true`

**示例5**

输入：`[5,4,3,2,1,6]`
输出：`false`

**解决方案**

我们可以使用一个栈来模拟压入和弹出操作。每次遇到一个数字，我们都将其压入栈中。如果当前栈顶元素与下一个预期的栈顶元素相同，则我们可以弹出栈顶元素，直到栈为空或栈顶元素不再匹配。

class Solution:
 def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
 stack = []
 j =0 for i in range(len(pushed)):
 stack.append(pushed[i])
 while stack and stack[-1] == popped[j]:
 stack.pop()
 j +=1 return not stack

**代码注释**

* 我们首先初始化一个空栈 `stack` 和一个索引 `j` 来跟踪弹出序列中的当前元素。
* 然后，我们遍历压入序列中的每个数字，并将其压入栈中。
* 每次遇到一个数字时，我们尝试匹配它与下一个预期的栈顶元素。如果它们相等，我们可以弹出栈顶元素，直到栈为空或栈顶元素不再匹配。
* 最后，我们检查栈是否为空。如果栈为空，则意味着压入和弹出序列是匹配的，因此我们返回 `True`。否则，我们返回 `False`。

**时间复杂度**

该算法的时间复杂度为 O(n)，其中 n 是压入序列中的数字数量。每个数字都被推送到栈中一次，弹出栈顶元素也只发生在匹配时，因此总共进行了 O(n) 次操作。

**空间复杂度**

该算法的空间复杂度为 O(n)，其中 n 是压入序列中的数字数量。我们使用一个栈来存储每个数字，最大可能大小是压入序列中数字的数量。