判断搜索树后序遍历是否合法（单调栈）

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

示例一：

输入: [1,6,3,2,5]
输出: false

示例二：

输入: [1,3,2,6,5]
输出: true

运用单调栈求解。
输入可能是某二叉搜索树的后序遍历，其可以看作 “左 | 右 | 根” 的组成顺序，若从后向前看，则是 “根 | 右 | 左” 的组成顺序，既然是二叉搜索树，那么必然有 “左 < 根 < 右” 的规则（暂不考虑相等），只要有一棵子树的左节点值大于根，或者右节点值小于根，则该后序遍历不合法，返回false，该算法就是基于此思路。下面给出算法步骤并作出解释：

从后向前遍历输入数组：

1. 若当前节点的值大于 last 的值（last 初始值为无穷大），则返回false，判断结束；
2. 若当前节点的值小于栈顶元素，则弹出栈顶元素 x，并更新 last = x，转 2；
3. 若当前节点的值大于栈顶元素，则将其压入栈，作为新的栈顶元素；
4. 遍历结束后返回 true。

当且仅当左子树合法以及右子树合法，并且满足左子树所有元素小于根，右子树所有元素大于根的时候（隐藏不等式 左子树所有值 < 右子树任意值 ），当前的后序遍历对应的搜索树才是合法的。

这些子树的后序遍历构成了整棵树的完整后序遍历，所以原数组其实可以看做是若干棵子树的后序遍历构成的，即 “左 | 右 | 根 | 左 | 右 | 根 | 左 | 右 | 根 …”，倒过来看就是 “根 | 右 | 左 | 根 | 右 | 左 | 根 | 右 | 左 …”，就当前子树来看，大小顺序是 “左 < 根 < 右” ，但是当前子树的最小值必然大于下一棵子树的最大值，因为这两棵子树可以看作一棵更大子树的 “右” 和 “左” 。

提示：
单调栈何时用：为任意一个元素找左边和右边第一个比自己大/小的位置用单调栈
用递增单调栈还是递减单调栈：递减栈会剔除波谷留下波峰；递增栈剔除波峰留下波谷

所以我们需要不断取出前一个子树的最小值 last ，看看它是不是比当前子树的最大值还要大，如果不满足，则必然不合法。由于根也是必然小于 last 的，所以干脆不特殊对待根，把他也归于左子树中，所以只需要判断 “所有左子树的值 < last” 是否成立即可，用单调栈判断。

测试地址

参考代码：

class Solution {
public:
    static const int N = 1007;
    static const int INF = 0x3f3f3f3f;
    int stack[N], top = 0;

    bool verifyPostorder(vector& postorder) {
        if(postorder.size() <= 2) return true;

        int n = postorder.size();
        int last = INF;     //初始值
        stack[++top] = -INF;  //设置边界

        for(int i = n-1;i >= 0;i--){
            if(postorder[i] > last) return false;

            while(postorder[i] < stack[top])
                last = stack[top--];
            
            stack[++top] = postorder[i];
        }
        return true;
    }
};