255.md

二叉搜索树的前序遍历有以下特点：

• 如果出现递减序列，则是左子树，否则是右子树；
• 右子树一定是递增的

综上，我们可以通俗理解为“总体递增，局部递减”。为了达到“总体递增的效果”，我们要保证递减序列的第一个元素小于递减结束后即将递增的那个元素。因此，我们我们使用new_min和栈，如果递减结束后，下一个元素小于递减序列的第一个元素，违背了“总体递增”，立即返回False。

• 76ms
• 96%
• time: O(n)
• space: O(n)

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        newMin = float("-inf")
        for i in preorder:
            if i < newMin: return False
            while stack and stack[-1]<i:
                newMin = stack.pop()
            stack.append(i)
        return True

• space: O(1)

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        minVal = float("-inf")
        i = -1
        for val in preorder:
            if val < minVal:return False
            while i>-1 and preorder[i] < val:
                minVal = preorder[i]
                i -= 1
            i += 1
            preorder[i] = val
        return True