题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
递归思路(java):
1.用两个指针指向最新的可入栈元素和目前想要从栈获取的元素;
2.每次尝试获取目标元素,成功则出栈并更新目标元素继续获取,失败则纳入可入栈元素并继续尝试获取当前目标元素
3.目标元素全部获取,则返回true
import java.util.Stack; //判断出栈序列是否合法 public class Solution { static int p1=0,p2=0;//p1指向最新的可入栈元素,p2指向想要从栈中获取的元素 static Stack<Integer> s=new Stack(); public boolean IsPopOrder(int [] pushA,int [] popA) { return fun(pushA,popA); } public boolean fun(int[] PA,int[] PB){ //如果栈为空,但还有想要取得的元素,则将p1所指入栈,并尝试获取p2所指 if(s.size()==0 && p2<=PB.length-1){ s.push(PA[p1]); p1++; System.out.println("入栈:"+s.peek()+" "+s); return fun(PA,PB); } //如果可以取得该元素 即p2所指 if(PB[p2]==s.peek()){ int ss=s.peek(); s.pop(); System.out.println("出栈:"+ss+" "+s.toString()); //如果后面还有待取元素,尝试获取 if(p2<=PB.length-2){ p2++; return fun(PA,PB); } //如果当前是最后一个元素,结束,合法 if(p2==PB.length-1){ return true; } } //如果无法取得该元素 if(PB[p2]!=s.peek()){ //如果已经没有可取元素,直接返回非法 if(p1==PA.length)return false; s.push(PA[p1]); System.out.println("入栈:"+s.peek()+" "+s); p1++; return fun(PA,PB); } return false; } }