🌕 剑指 Offer 31. 栈的压入、弹出序列

难度: 🌕

问题描述

---

解法

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 思路：
        // 借助 栈，模拟情景
        // 题意已经说明了所有元素均不想等，因此只有一种情况
        int len = pushed.length;
        if(len == 0) {
            return true;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        int i = 0;
        int j = 0;
        while(i < len && j < len) {
            // System.out.println(pushed[i] + " : " + popped[j]);
            int exp = popped[j]; // 当前需要弹出的节点值
            if(!stack.isEmpty() && stack.peek() == exp) {
                stack.pop();
                // i ++;
                j ++;
            } else if(pushed[i] == exp) {
                i ++;
                j ++;
            } else {
                // 持续压栈
                stack.push(pushed[i]);
                i ++;
            }
        }
        while(!stack.isEmpty()) {
            int val = stack.pop();
            int exp = popped[j];
            // System.out.println(val + "  " + exp);
            if(val != exp) {
                return false;
            }
            j ++;
        }
        return true;
    }
}

---

输出