The main problem is to investigate the characteristics of the stack, optimization can consider their own implementation of a stack.

The original problem

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]trueExplanation: we can perform in the following order: push (1), push (2), push (3), push (4), pop () - > 4, push (5), pop () - > 5, pop () - > 3, pop () - > 2, pop () - > 1Copy the code

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]falseExplanation: 1 cannot pop before 2. Length <= 1000 * 0 <= pushed[I], popped[I] < 1000 * pushed is an array of popped. Original url: https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/# # the problem solving

### Borrow the off-the-shelf Stack classSince the problem is to determine whether the Stack and Stack sequences match, we can directly use the existing 'Stack' class to simulate. The characteristics of the stack is' first in, then out ', so the number of the stack, want to be out of the stack: 1. After the stack, wait for all the numbers behind the stack out of the stack, and then out of the stack when the simulation, you can traverse the stack sequence, first let the current number into the stack, and then start to let the number in the stack out of the stack, if the stack sequence is satisfied, you can continue to out of the stack, until the stack can not be out. Let's look at the code:  ```Java class Solution { public boolean validateStackSequences(int[] pushed, Int [] popped) {// Stack<Integer> Stack = new Stack<>(); // popIndex = 0; // iterate over the stack sequencefor(int i = 0; i < pushed.length; I ++) {// Push the current number into the stack. Push (pushed[I]); / / traversal stackwhile (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
                popIndex++;
                stack.pop();
            }
        }
        
        returnpopIndex == pushed.length; }}Copy the code

OK.

Complexity analysis: time complexity O(N) : where N is the length of the tabled pushed; Each element can be pushed on and off the stack at most once, that is, a total of 2N operations on and off the stack. Ignoring the coefficients, we get O(N). Space complexity O(N) : Secondary stack stores a maximum of N elements at the same time.

Implement a simple stack structure yourself

We used the Stack class in Java, but because our scenario here is very simple, and the Stack takes into account capacity expansion and concurrent modification, performance will be affected accordingly. Therefore, we can design a simple stack structure with arrays.

In fact, the code is similar to the above, but because it is implemented directly using arrays, performance can be much faster for large numbers.

public boolean validateStackSequences(int[] pushed, int[] popped) {
    // Implement a stack using arrays
    int stack[] = new int[pushed.length];
    // The number of elements in the stack
    int stackSize = 0;
    // The index to which the stack sequence is iterated
    int poppedIndex = 0;
    // iterate over the stack sequence
    for (int i = 0; i < pushed.length; i++) {
        stack[stackSize] = pushed[i];
        stackSize++;
        // There is data in the stack, and the top element of the stack is equal to the number in the current stack exit sequence
        while(stackSize ! =0 && stack[stackSize - 1] == popped[poppedIndex]) {
            / / out of the stack
            stackSize--;
            // Move on to the next onepoppedIndex++; }}return poppedIndex == popped.length;
}
Copy the code

Submit OK, the complexity is exactly the same as above.

Of course, the difficulty of this problem can be improved. In the original problem, it is assumed that all the numbers pushed are not equal. If the numbers are allowed to repeat, can you think of how to solve this problem?

conclusion

This is the problem I solved the process, I don’t know if you understand. The main problem is to investigate the characteristics of the stack, optimization can consider their own implementation of a stack.

If you are interested, you can visit my blog or pay attention to my public number and headline number. Maybe there will be unexpected surprises.

death00.github.io/

Public account: The road to health