剑指offer-栈的压入、弹出序列

用了一种非常复杂的思路，代码比较长，感觉自己太菜了。。。

• 两序列长度不一样时，返回false
• 入栈序列或出栈序列为null，返回false
• 两个序列有不相同元素时，返回false
• 判断出栈序列是否是合理的入栈序列的出栈

思路：将入栈序列放入哈希表map中，形式是(a[i], i)；i是顺序下标，这么写的原因是序列的压栈顺序与序列的值大小关系并不对应，例如序列{6,1, 5}，对应的 map{(6,0), (1,1), (5,2)}.

给定出栈序列{1,5,6}，对应的压入索引是{1,2,0}。等价于判断{1,2,0}是不是{0,1,2}的一个出栈序列。

对于出栈序列，去掉第一个索引a后面的比a大的数，剩下的索引应该是递减的。原理是索引a如果先出栈，说明比它小的索引已经压好了，只能按照压入的逆序出栈。例如入栈：12345，出栈43521，第一个数是4，去掉后面的5，剩下4321，则该出栈是合法的；

若出栈43512,去掉5，剩下4312，则该出栈不合理。可以用类似冒泡的思想判断剩下的序列是否递减。

代码如下

import java.util.ArrayList;
import java.util.HashSet;
import java.util.HashMap;
import java.util.Set;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
      int len = pushA.length;
      int i, j;
      HashMap map = new HashMap();
      Set set = new HashSet();
      if(pushA.length != popA.length){
           return false;
      }
      if(pushA==null||popA==null){
            return false;
      }
      //如果数组中有不相等的元素 肯定不是
      for(int a:pushA){
          set.add(a);
      }
      for(int a:popA){
          if(!set.contains(a)){
              return false;
          }
      }
     for(i=0;i<len;i++){
         map.put(pushA[i],i);
     }
     for(i=0;i<len;i++){
         int temp=map.get(popA[i]);
         for(j=i;j<len-1;j++){
             if(map.get(popA[j+1])>temp){
                 continue;
             }
             if(map.get(popA[j])< map.get(popA[j+1])){
                 return false;
             }
         }
     }
     return true;
    }
}

简洁的做法是，将pushA的序列逐个压入栈中，压入之后判断是否与popA的元素相等，相等则出栈。循环完毕之后，栈空则说明popA是pushA的一个出栈顺序。

代码如下：

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack stack = new Stack();
        if(pushA.length != popA.length){
             return false;
        }
        if(pushA==null||popA==null){
              return false;
        }
        int len = pushA.length;
        int i;
        int j=0;
        for(i=0;i<len;i++){
            stack.push(pushA[i]);
            while(!stack.isEmpty() && popA[j]==stack.peek()&& j<len){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}