Topic describes

Enter two sequences of integers. The first sequence represents the push order of the stack. Determine whether the second sequence is the eject order of the stack. Assume that all the numbers pushed are not equal. For example, the sequence {1,2,3,4,5} is a pushdown sequence of a stack, and the sequence {4,5,3,2,1} is a corresponding pop-up sequence of the pushdown sequence, but {4,3,5,1,2} cannot be a pushdown sequence of the pushdown sequence.

Example 1: input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] output: true push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2: Input: Pushed = [1,2,3,4,5], popped = [4,3,5, 2] output: false Explanation: 1 cannot pop before 2.

1. Output in reverse order

  1. Find the popIdx of the element in the push order based on the first element in the push order
  2. Start loop the stack order and judge.
  3. If Pushed [popIdx] == popped[0], we remove 2 elements from 2 lists respectively and popidX-1
  4. If they’re not equal, popIdx + 1
  5. Finally, if the pushed list is empty, the pushed list is successfully pushed

When one element is pushed, the remaining elements can either be pushed further, which is step 3, or pushed further, which is step 4

Example code 1:

def validateStackSequences(self, pushed: [int], popped: [int]) - >bool:
    if not pushed and not popped:
        return True
    popIdx = pushed.index(popped[0]) Step # 1
    while popIdx < len(pushed) and pushed:
        if pushed[popIdx] == popped[0] :Step # 3
            pushed.remove(pushed[popIdx])
            popped.remove(popped[0])
            if popIdx > 0:
                popIdx -= 1
        else:
            popIdx +=1 Step # 4
    
    return len(pushed) <= 0

Copy the code

Solution 2: Auxiliary stack simulation

  1. Create a secondary stack to simulate pushing
  2. Loop through each element of the list
  3. We first add the loop to the secondary stack
  4. Loop through the auxiliary stack to determine whether the top element of the stack is equal to the current iterated element of the unstack list. If so, the top element of the stack is removed from the stack

The loop-assisted stack removal is similar to step 3 in Idea 1, where the remaining elements can continue to be removed from the stack, while the outermost loop to the list corresponds to step 4 in idea 1, which pushes the remaining elements onto the stack

Example code 2:

def validateStackSequences(self, pushed: [int], popped: [int]) - >bool:
    stack, i = [], 0 Step # 1
    for num in pushed:
        stack.append(num) Step # 3
        while stack and stack[-1] == popped[i]: Step # 4
            stack.pop()
            i += 1
    return not stack
Copy the code