Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Copy the code

Note:

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed are unique.
popped.length == pushed.length
popped is a permutation of pushed.
Copy the code

parsing

It seems that this week’s questions are out of the relationship with the stack, is also a series of it, the stack of test point is very common, just use this week’s questions practice hand.

Given two different integer arrays pushed and popped, return true if this may be the result of a series of pushed and popped elements on an original empty stack and then returned to the empty stack, otherwise return false.

In a nutshell, we started with an empty stack and gave two list operations, pushed and popped. If the operation is performed in either order, the empty stack is returned True.

First of all, we need to know a common sense that all the elements in the stack are “advanced and then out”. If this rule is returned, it must be an illegal stack. Therefore, in the pushed, element A was pushed before B, so A must be pushed after B in popped.

  • We define an empty list L as the initial list, then define an index I to traverse through pushed, and an index J to traverse through popped;
  • In a while loop, if L is not empty and the top of L’s stack is equal to popped[j], we pop the top of L’s stack and increment j to find the next popup; Otherwise, it means that there is no element that needs to be pushed, and we will push [I] into the top of the stack. Then I will add one to find the next element that needs to be pushed into the stack. And I keep going until I or J jumps out of the loop
  • When j is still less than the popped length, it means there are other elements to pop, so if popped[j] is equal to the top of L’s stack, pop L’s stack element, and then add j by one until J jumps out of the loop
  • Return True if L is null and False if L is not null

Time is O(N), space is O(N)

answer

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        L = []
        i = 0
        j = 0
        while i < len(pushed) and j < len(popped):
            if L and L[-1] == popped[j]:
                L.pop()
                j += 1
            else:
                L.append(pushed[i])
                i += 1
        while j < len(popped):
            if popped[j] == L[-1]:
                L.pop()
            j += 1
        return True if not L else False
        	      
		
Copy the code

The results

In the linked Python online submission for validated Stack Sequences. Memory Usage: 10 ms Given in Python online submissions for Validate Stack Sequences.Copy the code

The original link

Leetcode.com/problems/va…

Your support is my biggest motivation