題目

輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如，序列 {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 之前彈出。

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed?是?popped?的排列。

解題思路

1.題目要求我們判斷棧的彈出順序是否是所給兩個整數序列，對于這道題我們需要設置一個輔助棧來幫助我們。還需要一個變量k來指向我們的出棧元素，方便我們讀取。

2.舉個例子：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

我們先按入棧順序入棧第一個元素1

??

然后判斷stack當前的棧頂元素是否等于k指向的出棧順序的元素，若不等于我們就繼續入棧

?再次判斷stack當前的棧頂元素是否等于k指向的出棧順序的元素，不等于我們繼續入棧

?stack當前的棧頂元素依舊不等于k指向的出棧順序的元素，我們繼續入棧

??此時我們可以看到?stack當前的棧頂元素等于k指向的出棧順序的元素，我們就將Stack的棧頂元素出棧，并將 k 后移。

這時?stack當前的棧頂元素不等于k指向的出棧順序的元素，我們繼續按照入棧順序繼續入棧

再次將?stack當前的棧頂元素與k指向的出棧順序的元素進行判斷，發現兩者相等，我們就將棧頂元素進行出棧，并且將k后移

出棧

?

出棧

?

出棧

?

此時我們發現stack棧空了，那就證明所給的出棧順序是正確的。

3.本體的主要思想就是，我們需要查看棧頂元素是否與出棧順序所對應的元素相等，若相等就出棧，若不等就繼續按照入棧順序入棧，如果所有的操作結束后棧為空，就證明所給順序正確，否則就代表所給順序有誤。?

代碼實現

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {//判斷所給序列是否為空if(pushed == null || pushed.length == 0){return true;}//設置一個輔助棧Stack<Integer> stack = new Stack();int k = 0;for(int i = 0; i < pushed.length; i++){stack.push(pushed[i]);while(!stack.isEmpty() && stack.peek() == popped[k]){stack.pop();k++;} }return stack.isEmpty();}
}

測試結果

?