栈的压入、弹出序列（java）

没有使用模拟，根据pop序列在原序列中下标的升降顺序判断。 观察可以得到，如果pop序列是出栈的数列，序列在原序列的下标要么是全部降序，要么是先升序(升序过程中可以包含差值为1的降序)后降序。

思路：使用map记录原序列中数字所对应的下标index（题目中说明数组中数字都不相同）， 然后对pop序列遍历，判断进入降序后，是否有升序存在，如果有则返回false。代码如下

import java.util.*;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int length = pushA.length;
        if (length == 1) {
            return pushA[0] == popA[0];
        }
        //用map记录数字下标
        Map<integer,integer> map = new HashMap<integer,integer>();
        for (int i = 0; i &lt; length; i ++) {
            map.put(pushA[i], i);
        }

        boolean reduce = false;//用于记录是否进入降序
        for (int i = 1; i &lt; length; i++) {
            if (!map.containsKey(popA[i]) || !map.containsKey(popA[i-1])) return false;
            if (reduce &amp;&amp; map.get(popA[i]) - map.get(popA[i -1]) &gt; 0) return false;
            if (!reduce &amp;&amp; map.get(popA[i]) - map.get(popA[i -1]) &lt; -1) reduce = true;
        }
        return true;
    }
}
```</integer,integer></integer,integer>