【刷題-?？汀砍鰲?、入棧的順序匹配 (代碼+動態(tài)演示)

💗題目描述 💗:

輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<= pushV [i]<=1000

3. pushV 的所有數(shù)字均不相同

💗解釋 : 其實這個題目的意思就是把通常經(jīng)常遇見的判斷題 已知入棧順序(入棧的同時可以出棧),判斷不可能的出棧順序 ,封裝成一個方法,然后我們通過此方法,傳入 入棧順序 和 可能的出棧順序,方法返回 true 代表 該出棧順序是可能的, 返回false 代表 該出棧順序是不可能的 .

解題思路

遍歷入棧順序進行壓棧,壓棧之后遍歷可能的出棧順序,如果遍歷到的元素若與此時棧頂元素相同則表示應(yīng)該出棧,然后繼續(xù)后移判斷;若不相同則表示此時不用出棧,轉(zhuǎn)而繼續(xù)進行壓棧操作.

接下來我將通過動態(tài)圖演示具體的過程,同時會將偽代碼先寫出來

例子入棧順序 : 1  2  3  4  5 可能的出棧順序 : 4  3   5  1  2 

動圖演示

---

• 可能出現(xiàn)的bug

我們通過觀察偽代碼中的while循環(huán)語句的條件,我們并沒有考慮如果棧為空和 j 下標越界的情況 , 為什么要考慮這兩種情況呢 ?

原因 : 我們在需要對這個代碼進行測試 , 也就是看這個代碼是否滿足所有測試用例可能出現(xiàn)的情況.

---

當入棧順序和可能的出棧順序是相反的 : 可能的出棧順序② : 5  4  3  2  1入棧順序  : 1  2  3  4  5

當棧為空的時候,我們就不能再進入while循環(huán)的條件語句去執(zhí)行s.peek()==popV[j] 了,所以我們可以在while條件
中增加一個條件 && != s.empty()

---

當入棧順序和可能的出棧順序是相同的 :
可能的出棧順序③ : 1  2  3  4  5
入棧順序  : 1  2  3  4  5

此時在while循環(huán)中執(zhí)行完 s.pop() 之后,需要繼續(xù)執(zhí)行 j++ ,那么 j 就變成了 popV.length了. 所以此時我們不能進入while循環(huán)的條件語句去執(zhí)行s.peek() == popV[j] 了,因為此時的 j 會出現(xiàn)下標越界異常,所以我們可以增加一個條件 && j<popV.length

---

• 繼續(xù)完善

由于題目要求 0<=pushV.length == popV.length <=1000 那么我們給方法傳入的兩個數(shù)組參數(shù)是可能為空的,為了提升代碼的健壯性,我們可以可再繼續(xù)加一個 if 條件語句 <font color=‘red’ return false;`

---

完整代碼

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可** * @param pushV int整型一維數(shù)組 * @param popV int整型一維數(shù)組 * @return bool布爾型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;if(pushV.length == 0 || popV.length == 0) return false;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(j<popV.length&& !stack.empty() && stack.peek().equals(popV[j])){stack.pop();j++;}}return stack.empty();}
}

---

多組測試

• 測試一

• 測試二

• 測試三

• 測試四

---

求三連!!!