题目描述
看了一眼题解,发现大家的代码水平很高,我只能代表小白来给大家解构一下这个模拟的条件边界如何划分
模拟题
首先定义pushV和popV的操作指针idx1和idx2,用一个栈对popV的弹栈顺序进行处理
总共有4种情况:
1.idx1,idx2异常且stack不为空,说明无法还原,返回false
2.idx1,idx2异常且stack为空,说明可以还原,返回true
(由于前两点包含了idx1和idx2异常的情况,所以3、4的情况的idx1和idx2必然正常)
3.如果stack为空 或 栈顶元素不是popV[idx2]的元素,则继续寻找下一个
(由于3,则被排除的情况4,可以用else来表示,这里作一下解释)
4.如果当前stack不为空,栈顶元素雨popV[idx2]相同,则stack出栈,idx2右移一位
样例
import java.util.Stack;
public class Solution {
public boolean isPopOrder(int [] pushV,int [] popV) {
if (pushV.length!=popV.length){
return false;
}
if (pushV.length==0){
return true;
}
Stack<Integer> stack = new Stack<>();
int n = popV.length;
int idx1=0, idx2=0;
stack.push(pushV[idx1]);
while (true){
if ((idx1>=n || idx1<0 || idx2>=n || idx2<0) && stack.size()!=0){
return false;
}else if((idx1>=n || idx1<0 || idx2>=n || idx2<0) && stack.size()==0){
return true;
} else if (stack.size()==0 || stack.peek()!=popV[idx2]) {
idx1++;
if (idx1>=n || idx1<0) continue;
stack.push(pushV[idx1]);
}else {
stack.pop();
idx2++;
}
}
}
}