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

💗題目描述 💗:

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

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

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

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

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

解題思路

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

接下來(lái)我將通過(guò)動(dòng)態(tài)圖演示具體的過(guò)程,同時(shí)會(huì)將偽代碼先寫(xiě)出來(lái)

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

動(dòng)圖演示

---

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

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

原因 : 我們?cè)谛枰獙?duì)這個(gè)代碼進(jìn)行測(cè)試 , 也就是看這個(gè)代碼是否滿足所有測(cè)試用例可能出現(xiàn)的情況.

---

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

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

---

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

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

---

• 繼續(xù)完善

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

---

完整代碼

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請(qǐ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();}
}

---

多組測(cè)試

• 測(cè)試一

• 測(cè)試二

• 測(cè)試三

• 測(cè)試四

---

求三連!!!