验证栈序列

难度: Medium

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
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 之前弹出。

提示：

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

Submission

运行时间: 16 ms

内存: 16.1 MB

# class Solution:
#     def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
#         # 尝试1、在poped栈中寻找首个与pused栈尾相同的元素
#             # poped该元素前面的 以外的 pushed元素，在popped中需逆序
#         n = len(popped)
#         for pp in range(0, n):
#             if popped[pp] == pushed[-1]:
#                 break
#         pre_pp = popped[:pp]
#         pre_ps = []
#         for ps in range(0, n - 1):
#             if pushed[ps] not in pre_pp:
#                 pre_ps.append(pushed[ps])
#         for j in range(pp + 1, n):
#             if popped[j] in pre_ps:
#                 if popped[j] != pre_ps[-1]:
#                     return False
#                 pre_ps.pop()
#         if pre_ps:
#             return False
#         # 尝试2、pushed和poped进行匹配，如果pushed指针发生了跳跃，则跳过的数字需在poped中逆序
#         n = len(popped)
#         pp, ps, pre_pushed_copy = 0, 0, []
#         while pp < n:
#             if popped[pp] in pre_pushed_copy:
#                 pp += 1
#                 continue
#             pre_ps = ps
#             while ps < n and pushed[ps] != popped[pp]:
#                 ps += 1
#             if ps == n:
#                 ps = pre_ps
#             if ps > pre_ps + 1:
#                 pre_pushed = pushed[pre_ps + 1: ps]
#                 pre_pushed_copy = deepcopy(pre_pushed)
#                 for j in range(pp+1, n):
#                     if popped[j] in pre_pushed:
#                         if popped[j] != pre_pushed[-1]:
#                             return False
#                         pre_pushed.pop()
#             pp += 1
        
#         return True

# 官解：直接模拟出入栈！
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        st, j = [], 0
        for x in pushed:
            st.append(x)
            # 如果栈非空且栈顶元素与pop相同，出栈
            while st and st[-1] == popped[j]:
                st.pop()
                j += 1
        # 如果最后还剩元素，意味着没匹配上
        return len(st) == 0

Explain

题解采用了直接模拟栈的入栈和出栈操作的方法来验证序列是否有效。对于每一个pushed中的元素，都将其加入到栈中，然后检查栈顶元素是否与popped中当前位置的元素相同，如果相同则进行出栈操作，并移动popped的指针。这个过程会重复直到pushed中的所有元素都被处理过，或者直到popped中的所有元素都匹配完毕。最后，如果栈为空，则意味着popped序列可以通过一定的入栈和出栈顺序来实现，返回true；否则返回false。

时间复杂度: O(n)

空间复杂度: O(n)

# class Solution:
#     def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
#         st, j = [], 0  # st是用来模拟栈操作的列表，j是popped序列的索引
#         for x in pushed:  # 遍历pushed序列的每一个元素
#             st.append(x)  # 将当前元素压入模拟栈中
#             # 检查栈顶元素是否与popped中当前j指向的元素相同
#             while st and st[-1] == popped[j]:  # 如果相同，则执行出栈操作，并将j向后移动一位
#                 st.pop()
#                 j += 1
#         # 如果栈为空，则说明所有元素都正确匹配了popped序列，返回true
#         return len(st) == 0

Explore

在模拟栈操作的过程中，每次入栈后立即检查栈顶元素与popped中当前元素的相同性是为了模拟栈的实时出栈过程，这样可以即时处理栈中的元素是否需要出栈，使得算法效率更高。如果在全部入栈后再进行出栈检查，则无法正确模拟实际的栈操作顺序，因为实际的栈操作是边入栈边出栈，这种即时检查可以确保栈的状态随时符合popped序列的要求。如果延迟出栈检查，可能会错过正确出栈的时机，导致无法正确复现出栈序列，从而影响算法的正确性。

一个元素会在没有被弹出的情况下继续保持在栈中，主要是因为栈顶元素与popped中当前元素不匹配。这通常发生在还有其他元素需要先出栈的情况下。例如，如果popped序列中下一个期望的元素是当前栈中某个更深层位置的元素，那么栈顶元素以及可能的其他元素将暂时留在栈中，直到它们成为栈顶元素并与popped序列中的下一个目标元素匹配后才会出栈。

当pushed和popped序列中的元素相同但顺序完全相反时，例如pushed为[1,2,3,4,5]而popped为[5,4,3,2,1]，算法会表现得非常高效，因为每个元素入栈后紧接着就会被出栈。在这种情况下，栈的大小增长非常有限，每次入栈后几乎立即出栈，栈操作的复杂度很低。因此，这不是算法效率最低的情况，实际上这种情况算法效率相当高。算法效率最低的情况通常发生在需要频繁入栈和出栈，且栈大小频繁变化的情况下，例如pushed和popped序列交错复杂，导致栈元素频繁变动。