Nuggets team number online, help you Offer impromptu! Click on theCheck the details

1. Title Description

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:

The input

Pushed = [1,2,3,4,5], popped = [4,5,3,2,1]Copy the code

The output

true
Copy the code

Explanation: We can execute in the following order:

push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Copy the code

Example 2:

The input

Pushed = [1,2,3,4,5], popped = [4,3,5, 2]Copy the code

The output

false
Copy the code

Explanation: 1 cannot pop before 2.

prompt

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
Copy the code

Pushed is an array of popped.

Second, train of thought analysis

My train of thought

  1. How do I make sure the stack pops correctly?
    • Find the rule: every popup number, the popup number must be the original stack and his adjacent two numbers (corresponding to the two kinds of popup method: as soon as put into the popup, popup the previous element), so traverse the stack array, see if the elements behind him are adjacent in the stack. All the numbers we matched, we set it to the first number, so we get adjacent.
    • Unfortunately, the idea is wrong. For example, [0, 2, 1] [0, 1, 2]
  2. Try playing it

The best way of thinking

  • I thought it was complicated! Simulate the order of pop stacks against the queue of pop stacks (compare the order of pop stacks by trying to push the push stack itself into a secondary stack)
    1. You need a secondary stack, and push the push stacks into the secondary stack in order.
    2. When pushing a push into a secondary stack, compare the pop stack each time. If it is the same, the pop stack will pop first (when pop pops push, it will also pop at this location) and then compare the pop stack to the next one
    3. Until the end of the stack is found to be the same, indicating the success of the simulation, that is to prove!

AC code

How I wrote it:

/** * My version of the error: * The whole idea doesn't hold up if you think about it */
@Deprecated
public boolean validateStackSequencesWrong(int[] pushed, int[] popped) {
    if(pushed.length ! = popped.length) {return false;
    }
    int[] foundIndex = new int[pushed.length];
    for (int i = 0; i < popped.length - 1; i++) {
        int cur = popped[i];
        int next = popped[i + 1];
        // See if next is adjacent to a cur in pushed
        for (int j = 0; j < pushed.length; j++) {
            if (pushed[j] == cur) {
                boolean flag = false;
                // Find the previous one
                int preIndex = j - 1;
                while (preIndex >= 0) {
                    if(foundIndex[preIndex] ! =0) {
                        preIndex--;
                        continue;
                    }
                    // Find the previous neighbor
                    if (pushed[preIndex] == next) {
                        flag = true;
                        // The location will not be found next time
                        foundIndex[j] = 1;
                    }
                    break;
                }
                // The first one matches the first one
                if (flag) {
                    continue;
                }
                // Find the latter one
                int lastIndex = j + 1;
                while (lastIndex < pushed.length) {
                    if(foundIndex[lastIndex] ! =0) {
                        lastIndex++;
                        continue;
                    }
                    // Find the next neighbor
                    if (pushed[lastIndex] == next) {
                        flag = true;
                        // The location will not be found next time
                        foundIndex[j] = 1;
                    }
                    break;
                }
                if(! flag) {return false; }}}}return true;
}
Copy the code

Best written:

public boolean validateStackSequences(int[] pushed, int[] popped) {
    / / auxiliary stack
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    for(int num : pushed) {
        / / num into the stack
        stack.push(num);
        // Each time a number is pushed into the auxiliary stack, the elements of the pop are compared. If they are equal, the elements of the pop continue
        while(! stack.isEmpty() && stack.peek() == popped[i]) { stack.pop();// After pop, index +1, compare the next bit of popi++; }}// If the loop ends and the secondary stack is not exhausted, it indicates that the order is wrong
    return stack.isEmpty();
}
Copy the code

Four,

This kind of operation feels like or, you know, two iterations of the real operation.