目錄

1.題目描述

2.題解

方法1

方法2

---

1.題目描述

輸入兩個(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ù)字均不相同

示例：?

輸入：[1,2,3,4,5],[4,5,3,2,1]

返回：true

輸入：[1,2,3,4,5],[4,3,5,1,2]

返回：false

2.題解

方法1

思路分析：

判斷兩個(gè)序列是否符合入棧、出棧的次序，我們可以使用一個(gè)棧來模擬。

入棧：棧頂元素不等于出棧序列當(dāng)前元素

出棧：棧頂元素等于出棧序列當(dāng)前元素

具體過程：

?具體實(shí)現(xiàn)：

1.創(chuàng)建一個(gè)棧，來模擬入棧、出棧次序

2.使用i、j來遍歷pushV、popV數(shù)組，i < pushV.length，入棧

3.棧頂元素等于popV數(shù)組當(dāng)前元素時(shí)，出棧

4.遍歷完pushV數(shù)組后，判斷棧是否為空，棧為空，彈出序列為正確的出棧順序；反之，則為錯(cuò)誤的出棧順序

代碼實(shí)現(xiàn)：

public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);//判斷是否有元素出棧while(j < popV.length && !stack.empty()){int k = stack.peek();if(k == popV[j]){stack.pop();j++;}else{break;}}}return stack.empty();}
}

?

方法2

思路分析：

由于數(shù)組本身就可用于實(shí)現(xiàn)棧，我們可以將pushV數(shù)組當(dāng)作棧，使用p來標(biāo)記棧頂，

入棧：pushV[p](棧頂元素)不等于當(dāng)前出棧數(shù)組中元素，p++(入棧)

出棧：pushV[p](棧頂元素)等于當(dāng)前出棧數(shù)組中元素，p--(出棧)

具體過程：

具體實(shí)現(xiàn)：

1.使用p來標(biāo)識(shí)棧頂元素

2.使用i、j來遍歷pushV、popV數(shù)組，pushV[p](棧頂元素)不等于當(dāng)前出棧數(shù)組中元素，

pushV[p] = pushV[i]，p++

3.pushV[p](棧頂元素)等于當(dāng)前出棧數(shù)組中元素，p--

4.遍歷完pushV數(shù)組后，判斷p的大小，若p為0，則表示所有元素都已出棧，出棧序列為正確的出棧順序，返回true，否則，返回false

代碼實(shí)現(xiàn)：

public class Solution {public boolean IsPopOrder (int[] pushV, int[] popV) {int p = 0;//標(biāo)識(shí)棧頂int j = 0;//出棧序列下標(biāo)for(int n : pushV){pushV[p] = n;while( p>=0 && j < popV.length && pushV[p] == popV[j]){j++;p--;}p++;}return p==0;}
}

題目來自：

棧的壓入、彈出序列_?？皖}霸_?？途W(wǎng) (nowcoder.com)