題?描述

輸?兩個整數序列，第?個序列表示棧的壓?順序，請判斷第?個序列是否可能為該棧的彈出順序。假設壓?棧的所有數字均不相等。例如序列1,2,3,4,5 是某棧的壓?順序，序列4,5,3,2,1 是該壓棧序列對應的?個彈出序列，但4,3,5,1,2 就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的?度是相等的）

示例1
輸?：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
說明：可以通過push(1) => push(2) => push(3) => push(4) => pop() => push(5)=> pop() => pop() => pop() => pop()；這樣的順序得到 [4,5,3,2,1] 這個序列，返回 true

思路及解答

輔助棧模擬（推薦）

使用一個輔助棧來模擬壓入和彈出過程：

1. 初始化一個空棧和指向彈出序列的指針
2. 遍歷壓入序列，依次將元素壓入棧中
3. 每次壓入后，檢查棧頂元素是否等于當前彈出序列元素
   • 如果相等，則彈出棧頂元素并移動彈出序列指針
   • 重復此過程直到不相等為止
4. 最后檢查棧是否為空，為空則表示彈出序列可行

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        // 邊界條件檢查
        if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
            return false;
        }
        
        Stack<Integer> stack = new Stack<>(); // 輔助棧
        int popIndex = 0; // 彈出序列指針
        
        for (int pushValue : pushA) {
            stack.push(pushValue); // 壓入當前元素
            // 循環檢查棧頂是否等于當前彈出元素
            while (!stack.isEmpty() && stack.peek() == popA[popIndex]) {
                stack.pop(); // 彈出匹配元素
                popIndex++; // 移動彈出序列指針
            }
        }
        
        return stack.isEmpty(); // 棧空表示全部匹配
    }
}

• 時間復雜度： O(n)
• 空間復雜度： O(n) , 借助了額外的棧空間，最壞情況下會全部?棧。

雙指針法

利用原數組作為棧空間，通過雙指針模擬棧操作：

1. 使用壓入序列本身作為棧空間
2. 通過棧指針和彈出序列指針同步移動
3. 直接在原數組上進行"壓入"和"彈出"操作

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length) {
            return false;
        }
        
        int stackTop = -1; // 棧指針
        int popIndex = 0; // 彈出序列指針
        
        for (int pushValue : pushA) {
            pushA[++stackTop] = pushValue; // 利用原數組存儲
            // 檢查并"彈出"
            while (stackTop >= 0 && pushA[stackTop] == popA[popIndex]) {
                stackTop--;
                popIndex++;
            }
        }
        
        return stackTop == -1;
    }
}

• 時間復雜度?：O(n)
• ?空間復雜度?：O(1)，僅使用固定數量的指針變量