C++ 解法, 执行用时: 2ms, 内存消耗: 528KB, 提交时间: 2022-02-10

class Solution {
public:
    bool VerifyBST(vector<int>& sequence, int Seqstart, int Seqend) {
        if (Seqstart >= Seqend) return true;
        int rootVal = sequence[Seqend];
        int index = Seqstart;
        for (; index < Seqend; index++) {
            if (sequence[index] > rootVal) break;
        }
        int leftLen = index;
        for (; index < Seqend; index++) {
            if (sequence[index] < rootVal) return false;
        }
        return VerifyBST(sequence, Seqstart, leftLen - 1) && VerifyBST(sequence, leftLen, Seqend - 1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        int n = sequence.size();
        if (n <= 0) return false;
        if (n <= 2) return true;
        return VerifyBST(sequence, 0, n - 1);
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 560KB, 提交时间: 2022-02-10

class Solution {
public:
    bool check(vector<int> pushV, vector<int> popV) {
        int n=pushV.size();
        int i=0,j=0;
        stack<int> s;
        while(i<n) {
            s.push(pushV[i]);
            while(!s.empty()&&s.top()==popV[j]) {
                j++;
                s.pop();
            }
            i++;
        }
        return j==n;
    }
    
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        vector<int> inOrder(sequence);
        sort(inOrder.begin(), inOrder.end());
        return check(inOrder, sequence);
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 568KB, 提交时间: 2021-11-22

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
         if(sequence.size() == 0) return false;
         return check(sequence, 0, sequence.size());
    }
    
    bool check(vector<int> &sequence, int l, int r) {
        if(l >= r) return true;
        int root = sequence[r];    //当前子树节点
        //划分出右子树
        int j = r-1;
        while(j >= 0 && sequence[j] > root) j--;
        //检查左子树是不是存在大于根节点的数
        for(int i = 0; i <= j; i++) {
            if(sequence[i] > root) return false;
        }
        
        //分治法检查左子树和右子树
        return check(sequence, l, j) && check(sequence, j+1, r-1);
    }
};

Rust 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2021-07-24

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * 
        * @param sequence int整型一维数组 
        * @return bool布尔型
    */
    pub fn VerifySquenceOfBST(&self, sequence: Vec<i32>) -> bool {
                // write code here
        let mut sequence = sequence;
        if sequence.len() == 0 {
            return false;
        }
        if sequence.len() == 1 {
            return true;
        }
        let root = sequence.pop().unwrap();
        let mut index = sequence.len();
        for (idx, &val) in sequence.iter().enumerate() {
            if val > root {
                index = idx;
                break;
            }
        }
        if index != sequence.len() && sequence[index+1..].iter().any(|&x| x <= root) {
            return false;
        }


        if index == 0 {
            self.VerifySquenceOfBST(sequence[index..].to_vec())
        } else if index == sequence.len() {
            self.VerifySquenceOfBST(sequence[..index].to_vec())
        } else {
            self.VerifySquenceOfBST(sequence[..index].to_vec()) && self.VerifySquenceOfBST(sequence[index..].to_vec())
        }



    }
}

Rust 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2021-03-01

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * 
        * @param sequence int整型一维数组 
        * @return bool布尔型
    */
    pub fn VerifySquenceOfBST(&self, sequence: Vec<i32>) -> bool {
        // write code here
        if sequence.is_empty() {return false; }
        Self::verify(&sequence[..])
    }
    fn verify(seq: &[i32]) -> bool {
        let (piv_ref, seq) = match seq.split_last() {
            None => return true,
            Some( (piv_ref, seq) ) => (piv_ref, seq),
        };
        let mut mid = None;
        for (i, val_ref) in seq.iter().enumerate() {
            if *val_ref > *piv_ref {mid = Some(i); break;}
        }
        let mid = match mid {
            None => return Self::verify(seq),
            Some(mid) => mid,
        };
        for val_ref in seq[mid..].iter() {
            if *val_ref < *piv_ref {return false;}
        }
        let (l, r) = seq.split_at(mid);
        Self::verify(l) && Self::verify(r)
    }
}