题目

• 概述：给定一个入栈序列和出栈序列，判断如果以入栈序列的顺序入栈，所给定的出栈序列的顺序是否是合理的

• 输入：入栈序列和出栈序列

  1. 序列长度一致，范围为[0, 1000]
  2. 入栈序列是出栈序列的排列

• 输入子项：[0, 1000)的整数

• 输出：对于所给定的入栈序列，出栈序列合理返回true，否则返回false

• 出处：https://leetcode-cn.com/problems/validate-stack-sequences/

思路

• 遍历出栈序列

1. 若当前出栈项在未入栈的序列中，则依次将未入栈的序列到该项为止的数（不包括该项）入栈

2. 若当前出栈项不在未入栈的序列中，则将栈中元素依次出栈直至出栈元素等于当前出栈项

   若未在栈中找到对应的出栈项，则该出栈序列不合理，返回false

3. 如果能够正确遍历完出栈序列，则证明出栈序列合理，返回true

4. 用map存储未入栈序列，使得能够快速判断当前出栈项是否在未入栈的序列中，并在入栈的过程中更新map

代码

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        Integer appearCnt;
        for (int i = 0; i < pushed.length; ++i) {
            appearCnt = map.get(pushed[i]);
            if (appearCnt == null) {
                map.put(pushed[i], 1);
            } else {
                map.put(pushed[i], appearCnt + 1);
            }
        }
        
        int j, splitIndex = 0;
        boolean popSuccess;
        for (int i = 0; i < popped.length; ++i) {
            if (map.get(popped[i]) != null) {
                for (j = splitIndex; j < pushed.length; ++j) {
                    appearCnt = map.get(pushed[j]);
                    if (appearCnt > 1) {
                        map.put(pushed[j], appearCnt - 1);
                    } else {
                        map.remove(pushed[j]);
                    }
                    if (pushed[j] == popped[i]) {
                        splitIndex = j + 1;
                        break;
                    }
                    stack.push(pushed[j]);
                }
            } else {
                popSuccess = false;
                while (!stack.isEmpty()) {
                    if (stack.pop() == popped[i]) {
                        popSuccess = true;
                        break;
                    }
                }
                if (!popSuccess) {
                    return false;
                }
            }
        }
        
        return true;
    }
}