本文共 2563 字，大约阅读时间需要 8 分钟。

题目难度: 中等

今天继续更新剑指 offer 系列, 这道题挺有意思的, 需要反其而行之, 这里依然提供两种方案供大家参考, 特别是方法 2, 对空间复杂度做了优化, 值得一读

老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

• 0 <= pushed.length == popped.length <= 1000
• 0 <= pushed[i], popped[i] < 1000
• pushed  是  popped  的排列。

题目样例

示例 1

输入

pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输出

true

解释

我们可以按以下顺序执行：

示例 2

输入

pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

输出

false

解释

1 不能在 2 之前弹出。

题目思考

1. 直接模拟整个过程可行吗?
2. 有没有不使用额外空间的做法?

解决方案

方案 1

思路

• 我们可以尝试使用一个栈模拟整个过程, 看看模拟过程中能否满足两个序列的顺序
• 对于每个压入序列, 我们直接将其压入栈中
• 而对于弹出序列, 我们需要额外维护一个指针, 指向当前要弹出的元素下标, 显然该指针初始化为 0
• 接下来比较栈顶是否和当前指针指向的元素是否相同, 相同的话弹出并让指针后移一位
• 重复上述过程直到遍历完整个压入序列
• 那么如果两个序列匹配的话, 最终的栈应该为空的.
  • 注意这里无需判断弹出序列是否也遍历完(即指针指向最后一个元素后一位), 因为如果栈为空的话代表每个 push 都对应一个 pop, 而两个序列长度相等, 所以此时弹出序列肯定也遍历完了.
• 而如果最终的栈不为空, 则说明弹出序列不对了, 卡在了某个下标处, 本应该先弹当前栈顶的, 结果弹出序列的当前元素不是栈顶, 无法正常弹出.

复杂度

• 时间复杂度 O(N)
  • 每个元素只会被压入和弹出栈一次
• 空间复杂度 O(N)
  • 额外需要一个栈

代码

class Solution:    def validateStackSequences(self, pushed: List[int],                               popped: List[int]) -> bool:        # 方法1: 利用栈模拟, 额外使用一个指针存储当前弹出序列位置        stack = []        j = 0        for p in pushed:            stack.append(p)            while stack and j < len(popped) and stack[-1] == popped[j]:                # 当前栈顶恰好等于当前弹出序列对应的元素, 栈弹出, 指针后移                stack.pop()                j += 1        # 如果栈为空则说明这两个序列有效        return not stack

方案 2

思路

• 回顾方案 1, 我们需要额外一个栈来老老实实模拟整个过程, 有没有不需要额外空间的做法呢?
• 答案也是肯定的, 方案 1 中的栈的目的就是模拟压入弹出过程, 整个遍历一遍压入队列, 我们其实可以直接利用压入队列来作为这个栈, 然后栈顶就用新的一个指针来代替即可, 这样就不需要额外空间了
• 其他思路和方案 1 相同, 入栈相当于当前压入队列指针的赋值+后移, 而出栈则简单的等同于压入队列指针的前移
• 最终就是判断栈顶指针是否为-1 来判断栈是不是空

复杂度

• 时间复杂度 O(N)
  • 每个元素只会被压入和弹出栈一次
• 空间复杂度 O(1)
  • 使用常数个变量

代码

class Solution:    def validateStackSequences(self, pushed: List[int],                               popped: List[int]) -> bool:        # 方法2: O(1)空间, 将pushed本身当作栈, 用一个下标表示当前栈顶, 双指针        topindex, j = -1, 0        for i in range(len(pushed)):            # 压入新元素, 所以需要先将栈顶指针后移一位, 然后赋值            topindex += 1            pushed[topindex] = pushed[i]            while j < len(popped) and topindex >= 0 and pushed[                    topindex] == popped[j]:                # 当前栈顶恰好等于当前弹出序列对应的元素, 栈顶指针前移, 弹出队列指针后移                topindex -= 1                j += 1        # 如果栈顶指针为-1, 说明栈为空, 也即这两个序列有效        return topindex == -1

大家可以在下面这些地方找到我~😊

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊

转载地址：https://blog.csdn.net/zjulyx1993/article/details/107344897 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！