leetcode-946：验证栈序列

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    int* arr = (int*)malloc(sizeof(int) * pushedSize);
    for(int i = 0; i < poppedSize; i++) arr[i] = 1;
    int ind = 0;
    for(int i = 0; i < poppedSize; i++){
        while(arr[ind] == 0 || popped[i] != pushed[ind]) {
            ind++;
            if(ind == poppedSize) return false;
        }
        arr[ind] = 0;
        while(ind > 0 && arr[ind] == 0) ind--;
    }
    return true;
}

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    int* sta = (int*)malloc(sizeof(int) * poppedSize);
    int top = -1, x = 0;
    for(int i = 0; i < poppedSize; i++){
        if(top == -1 || sta[top] != popped[i]){
            while(x < poppedSize && pushed[x] != popped[i]){
                sta[++top] = pushed[x++];
            }
            if(x == poppedSize) return false;
            sta[++top] = pushed[x++];
        }
        top--;
    }
    return true;
}

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    int* sta = (int*)malloc(sizeof(int) * poppedSize);
    int top = -1, x = 0;
    for (int i = 0; i < poppedSize; i++){
        while(top == -1 || sta[top] != popped[i]){
            if(x == poppedSize) return false;
            sta[++top] = pushed[x++];
        }
        top--;
    }
    return true;
}

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n = pushed.size(), x = 0;//x代表入栈序列的下标
        stack<int> s;
        for(int i = 0; i < n; i++) {
            if (s.empty() || s.top() != popped[i]) {
                while (x < pushed.size() && pushed[x] != popped[i]) {
                    s.push(pushed[x]);
                    x += 1;
                }
                if (x == pushed.size()) return false;
                s.push(pushed[x]);
                x += 1;
            }
            s.pop();
        }
        return true;
    }
};