题解 | #栈的压入、弹出序列#

import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if (pushA.length <= 0) {
            return false;
        }
        Stack<Integer> stk = new Stack<>();

        int j = 0;    // 用j指针指向popA数组中待处理的每个元素
        int k = 0;    //用k指针指向pushA数组
        /*
            大致思路：首先找到push数组中第一个等于popA[j]（j从0开始）的元素（假设pushA数组中第k个数为该元素），
            因为popA[0]第一个出栈，所以要将pushA数组中前k个元素全部入栈，然后将pushA[k]出栈，接着j++,判断
            栈顶元素是否为popA[j]，如果是就出栈。继续判断下一个元素，如果不是，就遍历pushA,如果pushA[k]不等于popA[j]，
            那么就入栈，直到找到值为popA[j]的pushA[k]。最后，判断栈是否为空，并且确认已经遍历完成，如果为空栈，说明popA
            的序列为正常出栈序列， 否则为错误出栈序列
            
        */
        
        
        for (; k < pushA.length; k++) {
            if (pushA[k] != popA[0]) {
                stk.push(pushA[k]);
            } else {
                break;
            }
        }
        k++;
        j++;
        
        while (j < popA.length) {
            int temp;
            if (!stk.empty()) {
                temp = stk.pop();
                if (temp == popA[j]) {
                    j++;
                    continue;
                }
                stk.push(temp);
            }
            
            while (k < pushA.length) {
                if (pushA[k] != popA[j]) {
                    stk.push(pushA[k]);
                } else {
                    k++;
                    break;
                }
                k++;
            }
            j++;
        }
        if (k >= pushA.length && stk.empty()) {
            return true;
        } else {
            return false;
        }
        
    }
}