Jianbo Dai's

jz031.栈的压入、弹出序列

 
  • Jun 14, 2020

题目链接

解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。具体来说，算法1描述的思路就是，检查popped的每一个元素，如第一个元素，判断其是否在辅助栈中，若是，则将改元素弹出并检查poped中的下一个元素；若不是，则将pushed中的元素依此压入辅助栈中直到压入的数字与正在检查的元素相同时，弹出这个元素并检查下一个元素。当pushed中的所有元素都被压入辅助栈但poped中还有元素剩余时，返回False，或当popped已经遍历结束但pushed中还有元素剩余时，也返回False，反之返回True。这个算法的时间复杂度是O（N），空间复杂度是O（N）。

不过我这个思想比较别扭，其实算法2就是比较正常的思路，就是我在第一段首写的，依此将数字压入栈，依此判断是否与popped中的元素相同，若相同则弹出，若不同则继续压入pushed中的下一个数字。将所有操作都执行后，若辅助栈重新为空，则返回True。

class Solution:
    def validateStackSequences1(self, pushed: List[int], popped: List[int]) -> bool:
        auxillaryStack = []
        for i in popped:
            while not auxillaryStack or i != auxillaryStack[-1]:
                if not pushed:
                    return False
                else:
                    auxillaryStack.append(pushed.pop(0))
            auxillaryStack.pop()
        if not pushed:
            return True
        else:
            return False

class Solution:
    def validateStackSequences2(self, pushed: List[int], popped: List[int]) -> bool:
        stack, i = [], 0
        for num in pushed:
            stack.append(num) # num 入栈
            while stack and stack[-1] == popped[i]: # 循环判断与出栈
                stack.pop()
                i += 1
        return not stack
Search