【java】劍指offer31_棧的壓入、彈出序列

題目描述：

輸入兩個整數序列，第一個序清單示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如，序列 {1,2,3,4,5} 是某棧的壓棧序列，序列 {4,5,3,2,1} 是該壓棧序列對應的一個彈出序列，但 {4,3,5,1,2} 就不可能是該壓棧序列的彈出序列。

示例 1：

輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

輸出：true

解釋：我們可以按以下順序執行：

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

輸出：false

解釋：1 不能在 2 之前彈出。

提示：

0 <= pushed.length == popped.length <= 1000

0 <= pushed[i], popped[i] < 1000

pushed 是 popped 的排列。

參考解題思路：利用棧後進先出的特性，借用一個輔助棧deque ，模拟 壓入 / 彈出操作的排列 

• 入棧操作： 按照壓棧序列的順序執行。
• 出棧操作： 每次入棧後，循環判斷 “棧頂元素 == 彈出序列的目前元素” 是否成立，将符合彈出序列順序的棧頂元素全部彈出

1.初始化： 輔助棧 deque ，彈出序列的索引 index；

2.周遊壓棧序列： 各元素記為num ；

• 元素 num 入棧；
• 循環出棧：若 deque 的棧頂元素 == 彈出序列元素popped[i] ，則執行出棧與i++ ；

3.傳回值： 若 deque為空，則此彈出序列合法。

public boolean validateStackSequences(int[] pushed, int[] popped) {
        int index = 0; // 下标移動
        Deque<Integer> deque = new ArrayDeque<>(); // 輔助棧
        // 周遊壓入棧
        for (int i : pushed) {
            deque.push(i); // 壓入輔助棧
            // 判斷壓入棧頂資料是否與退出棧頂資料相等
            while (!deque.isEmpty() && deque.peek() == popped[index]) {
                index++; // 退出棧下邊往後移動--判斷下一位
                deque.pop(); // 輔助棧彈出相等棧頂元素
            }
        }
        // 輔助棧為空則全部元素退完--則相等傳回true
        return deque.isEmpty();
    }
           

複雜度分析：

時間複雜度 O(N)： 其中 N為清單 pushed的長度；每個元素最多入棧與出棧一次，即最多共 2N 次出入棧操作。

空間複雜度 O(N) ： 輔助棧deque 最多同時存儲 N個元素。

作者：jyd

連結：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2/