最大二叉树（Leetcode）-最优解解释？

Question

我正在解决leetcode的最大二叉树问题。TL;DR 是你有一个数组，例如这个：

[3,2,1,6,0,5]

您应该获取最大元素并将其作为树的根。然后将数组分为该元素左侧的部分和右侧的部分，这些部分分别用于以相同的方式递归创建左子树和右子树。

LeetCode 声称最佳解决方案（显示在“解决方案”选项卡中）在每个递归步骤中使用线性搜索来寻找子数组的最大值。在最坏的情况下，这是 O(n^2)。这是我想出的解决方案，而且很简单。

然而，我正在查看其他提交的内容并找到了线性时间解决方案，但我很难理解它是如何工作的！它看起来像这样：

def constructMaximumBinaryTree(nums):

    nodes=[]

    for num in nums:

        node = TreeNode(num)

        while nodes and num>nodes[-1].val:

            node.left = nodes.pop()

        if nodes:

            nodes[-1].right = node

        nodes.append(node)

        

    return nodes[0]

nodes我已经分析了这个函数，总的来说，这似乎是线性时间 (O(n))，因为每个唯一节点最多添加到数组中并从数组中弹出一次。我尝试使用不同的示例输入来运行它，但我正在努力将这些点连接起来并理解它是如何工作的。有人可以向我解释一下吗？

Answer 1

理解该算法的一种方法是考虑循环不变量。在这种情况下， 的数组nodes始终满足在每次执行 之前和之后的条件for-loop：nodes为空且最大二叉树不存在（例如，如果输入nums为空）中的第一项nodes是基于迄今为止从输入处理的数据的最大二叉树nums确保while-loop当前最大二叉树是数组中的第一项nodes，否则，它将被弹出并添加为left子树。在 的每次迭代期间for-loop，检查：if nodes:     nodes[-1].right = node将当前节点作为右子树添加到数组中的最后一项nodes。当发生这种情况时，当前节点小于数组中的最后一个节点nodes（因为每个输入整数被定义为唯一）。并且由于当前节点小于数组中的最后一个节点，因此最后一个节点充当其值大于当前项的分区点，这就是为什么将当前节点添加为右子树。当数组中有多个项目时nodes，每个项目都是其左侧项目的子树。运行时间对于运行时间，令n为输入的长度nums。for 循环执行了n次。如果输入数据按降序排序，但最大输入值位于输入末尾（例如：4、3、2、1、5），则每次迭代期间将跳过内部 while 循环，直到最后一次 for 循环迭代。在最后一次 for 循环迭代期间， while 循环将运行n - 1次，总运行时间为n + (n - 1) => 2n - 1 => O(n)。