Algorithm Tip: Stack generative problem

Problem description

Given two sequences of pushed and popped, the values in each sequence are not repeated to determine whether they can perform push and pop operations on the initially empty stack. LeetCode (946).

Example: pushed = [1, 2, 3, 4, 5], popped =,5,3,2,1 [4] – > true

Pushed = [1, 2, 3, 4, 5], popped =,3,5,1,2 [4] – > false

The premise

First of all, we know:

1. When an item is removed from the stack, the item before it must have been removed from the stack (or removed from the stack).
2. If a number x is pushed and y before it is pushed does not pop before x is pushed, it must pop after X is pushed.

Train of thought

From these two points we can conclude: (assuming that the pushed is in positive order) If the operation can be achieved, this cannot happen in popped:

Let a< B < C, popped… C, a, B… This sequence. (If C is off the stack, a and B are already on the stack (premise 1), A is not popped before C is off the stack, i.e. A is not popped before B is on the stack, then A must pop after B is off the stack (premise 2), so B must be before A in popped, so C, A, B is impossible)

Therefore, the operation can be realized if the structure C, A, B does not appear in popped (there can be other numbers between C, A, and B).

However, because the judgment sequence is too complex, the time required is too much, far from our requirements, so the above ideas

Applies only to the human eye judgment, not to the program

The following procedure is given to determine the way.

The problem solving process

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
         stack<int>temp;
    int j = 0;
    for (auto i = 0; i < pushed.size();) {
        temp.push(pushed[i]);
        ++i;
        while (temp.size()! =0&&temp.top() == popped[j]) {
            temp.pop(a); ++j; }// Loop determines when popped pops pops pops pops pops pops.
    }
    if (temp.size() = =0) {
        return true;
    }
    return false;
    }
Copy the code

Their thinking

It directly simulates the process of loading and unloading the subject, cyclic loading and unloading, in which if top is the same as the element in the unloading sequence that you want to unstack now, then unstack. If the operation can be executed, the stack is empty at the end of the execution. The time is O(N) because there is only one loop to the stack, and the space is O(N) because there is only one stack for the elements.