輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否可能為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如序列 1,2,3,4,5 是某堆疊的壓入順序，序列 4,5,3,2,1 是該壓堆疊序列對應的一個彈出序列，但 4,3,5,1,2 就不可能是該壓堆疊序列的彈出序列，（注意：這兩個序列的長度是相等的）
不需要想太復雜，既然題目已經給出堆疊的壓入和彈出順序，那就模擬這個程序好了，可以借用一個輔助堆疊來實作，
舉個例子，入堆疊 1,2,3,4,5，出堆疊 4,5,3,2,1，程序如下：
- 首先 1 入輔助堆疊，此時堆疊頂 1 ≠ 4，繼續入堆疊 2
- 此時堆疊頂 2 ≠ 4，繼續入堆疊 3
- 此時堆疊頂 3 ≠ 4，繼續入堆疊 4
- 此時堆疊頂 4＝4，出堆疊 4，指向彈出的坐標向后一位，此時為 5，輔助堆疊里面是 1,2,3
- 此時堆疊頂 3 ≠ 5，繼續入堆疊 5
- 此時堆疊頂 5 = 5，出堆疊 5，彈出序列向后一位，此時為 3，輔助堆疊里面是 1,2,3
... - 依次執行，最后輔助堆疊為空，如果不為空說明彈出序列不是該堆疊的彈出順序
import java.util.Stack;
public class Solution {
private Stack<Integer> stack = new Stack<>();
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0) {
return false;
}
int popIndex = 0;
for(int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while(!stack.isEmpty() && stack.peek() == popA[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/177310.html
標籤：其他