LeetCode 255. 验证前序遍历序列二叉搜索树（单调栈）*

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3
示例 1：
输入: [5,2,6,1,3]
输出: false

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

进阶挑战：
您能否使用恒定的空间复杂度来完成此题？

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
    	if(preorder.size() <= 2) return true;
    	return check(preorder, preorder[0], 1, preorder.size()-1);
    }

    bool check(vector<int>& arr, int root, int l, int r)
    {
    	if(l>=r) return true;
    	int split = l, i;
    	while(split <= r && arr[split] < root)
    		split++;//左边部分比我root小
    	i = split;
    	for(i = split; i <= r; ++i)
    		if(arr[i] < root)//右边部分因该都比我大，此处复杂度较高
    			return false;
    	return check(arr, arr[l], l+1, split-1) && (split > r ||check(arr, arr[split], split+1, r));
    }
};

class Solution {
	map<int,int> m;
public:
    bool verifyPreorder(vector<int>& preorder) {
    	if(preorder.size() <= 2) return true;
    	int MIN = INT_MIN;
    	stack<int> s;
    	for(int i = 0; i < preorder.size(); ++i)
    	{
    		if(preorder[i] < MIN)
    			return false;
    		while(!s.empty() && s.top() < preorder[i])//遇到大的了，右分支
    		{
    			MIN = s.top();//记录弹栈的栈顶为最小值
    			s.pop();
    		}
    		s.push(preorder[i]);
    	}
    	return true;
    }
};