問(wèn)題描述
輸入兩個(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：
輸入：pushed = [1,2,3,4,5]
popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執(zhí)行：
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 之前彈出加叁。
問(wèn)題分析
這題主要考察對(duì)棧的理解倦沧，棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，如果棧頂元素不出棧它匕，那么棧頂元素下面的元素都是不能出棧的展融。
一種解決方式就是把pushed數(shù)組的元素逐個(gè)壓棧，當(dāng)棧頂元素等于popped數(shù)組中第一個(gè)元素的時(shí)候豫柬，就讓棧頂元素出棧告希，這個(gè)時(shí)候再用popped數(shù)組的第2個(gè)元素和棧頂元素比較扑浸，如果相同繼續(xù)出棧……燕偶，最后判斷棧是否為空即可喝噪，來(lái)看下代碼
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> pushStack = new Stack<Integer>();
int popIndex = 0;
for(int i = 0;i < pushA.length;i++){
pushStack.push(pushA[i]);
while(!pushStack.isEmpty() && popA[popIndex]==pushStack.peek()){
pushStack.pop();
popIndex++;
}
}
return pushStack.isEmpty();
}
}
另一種解決方式就是排除不可能的popped序列組合，解決思路如下：
在pushed數(shù)組中指么，如果排在當(dāng)前入棧元素后面的多個(gè)元素也入棧了酝惧，則后面的多個(gè)入棧元素必定先出棧，否則不符合出棧的特性伯诬。
因此晚唇，我們可以一開(kāi)始就記錄下入棧元素的初始下標(biāo)，使用map結(jié)構(gòu)盗似，key：入棧元素值缺亮，value：入棧元素的初始下標(biāo)。
排除不可能的情況：
遍歷出棧數(shù)組中的每一個(gè)元素桥言，如果當(dāng)前出棧元素的下標(biāo)(currIndex)與前一個(gè)出棧元素的下標(biāo)(beforeIndex)差的絕對(duì)值大于1或與后一個(gè)出棧元素的下標(biāo)(afterIndex)差的絕對(duì)值大于1萌踱，滿足beforeIndex > currentIndex ，則currentIndex > afterIndex 才符合出棧特性号阿。所以我們要排除beforeIndex > currentIndex && currentIndex < afterIndex的情況并鸵。
注意：beforeIndex < currentIndex 則 currentIndex 與 afterIndex的大小無(wú)特別要求。
如果pushed數(shù)組長(zhǎng)度<=1需要單獨(dú)考慮扔涧。長(zhǎng)度為1沒(méi)法前后比較园担，只需要判斷pushed和popped數(shù)組元素值是否相等即可。
代碼實(shí)現(xiàn)如下：
import java.util.*;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
// 如果pushA長(zhǎng)度小于等于1需要單獨(dú)判斷
if(pushA.length == 0 && popA.length == 0){
return true;
}
if(pushA.length == 1 && popA.length == 1){
return pushA[0] == popA[0];
}
// pushA的value和index存入map
Map<Integer,Integer> pushMap = new HashMap<>();
boolean result = true;
for(int i = 0;i < pushA.length;i++){
pushMap.put(pushA[i],i);
}
// 不符合情況排除
for(int i = 1;i < popA.length-1;i++){
int currIndex = pushMap.get(popA[i]);
int beforeIndex = pushMap.get(popA[i-1]);
int afterIndex = pushMap.get(popA[i+1]);
if(Math.abs(currIndex - beforeIndex) > 1 || Math.abs(currIndex - afterIndex) > 1){
if(currIndex < beforeIndex && currIndex < afterIndex){
result = false;
break;
}
}
}
return result;
}
}
