問題描述
輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如，序列 {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 的排列，
解題思路（模擬堆疊）：
本題輔助堆疊 stack ，模擬 壓入 / 彈出操作的排列，根據是否模擬成功，即可得到結果，
入堆疊操作： 按照壓堆疊序列的順序執行，
出堆疊操作： 每次入堆疊后，回圈判斷 “堆疊頂元素
彈出序列的當前元素” 是否成立，將符合彈出序列順序的堆疊頂元素全部彈出，
由于題目規定 堆疊的所有數字均不相等 ，因此在回圈入堆疊中，每個元素出堆疊的位置的可能性是唯一的（若有重復數字，則具有多個可出堆疊的位置），因而，在遇到 “堆疊頂元素 == 彈出序列的當前元素” 就應立即執行出堆疊
演算法整體思路：
1、首先，構造一個輔助堆疊
2、遍歷pushed陣列，每輪將pushed陣列中的元素一一入堆疊
3、對比popped陣列中的元素，如果順序一致，就將pushed陣列中的元素彈出
4、最終，判斷 堆疊中是否還有元素剩余 即可
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int len=pushed.length;
//構造一個模擬堆疊
Stack<Integer> stack =new Stack<Integer>();
int j=0;
//遍歷pushed陣列，每趟回圈將pushed陣列中的元素一一入堆疊
for(int i=0;i<len;i++){
stack.push(pushed[i]);
//如果堆疊頂元素等于彈出序列的當前元素，將符合彈出序列的堆疊頂元素一一彈出，
while(!stack.empty() && stack.peek()==popped[j]){
stack.pop();
j++;
}
}
//如果堆疊中還有剩余元素，則彈出序列不滿足要求，回傳false
if(!stack.empty()){
return false;
}
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/263435.html
標籤：java