最大二叉树为什么可以用分治构造？如何优化找最大值？

简化版

最大二叉树的根是当前数组区间的最大值。

最大值左边的部分递归构造左子树，右边的部分递归构造右子树，这就是天然分治。

直接每次扫描最大值最坏是 O(n^2)；如果要优化，可以用单调栈做到 O(n)。

详细版

递归函数 build(l, r) 表示用 nums[l..r] 构造最大二叉树。

如果区间为空，返回 null。否则扫描区间找到最大值下标 maxIdx，创建根节点，再递归构造：

left = build(l, maxIdx - 1)
right = build(maxIdx + 1, r)

这个分治很直观，但若数组单调递增，每次最大值都在边界，扫描成本累计为 O(n^2)。

面试中先讲分治构造，再补充单调栈优化，会比较完整。

完整版教学

一、为什么最大值必须做根

最大二叉树定义规定：根节点是数组最大值，左子树由最大值左边子数组构造，右子树由右边子数组构造。因此根的选择没有自由度。每确定一个根，原问题就被切成左右两个独立子问题。

记忆钩子：最大二叉树不是搜索树，它按“最大值切数组”生成。

二、分治结构如何递归

对任意区间 [l,r]，找到最大值位置 p。p 左侧元素在原数组中位于最大值左边，只能属于左子树；p 右侧元素只能属于右子树。左右两边又按同样规则构造最大二叉树。

区间部分	去向	原因
最大值	根节点	定义要求
最大值左侧	左子树	保持原相对位置
最大值右侧	右子树	保持原相对位置

这就是分治切分依据。

三、代码模板

直接分治实现如下：

function constructMaximumBinaryTree(nums) {
  function build(l, r) {
    if (l > r) return null
    let maxIdx = l
    for (let i = l + 1; i <= r; i++) {
      if (nums[i] > nums[maxIdx]) maxIdx = i
    }
    const root = new TreeNode(nums[maxIdx])
    root.left = build(l, maxIdx - 1)
    root.right = build(maxIdx + 1, r)
    return root
  }
  return build(0, nums.length - 1)
}

这段代码最贴近定义，适合先用来解释思路。

四、复杂度为什么可能退化

如果数组是 [1,2,3,4,5]，每次最大值都在最右边。第一次扫描 5 个元素，第二次扫描 4 个，之后是 3、2、1，总成本接近：

5 + 4 + 3 + 2 + 1 = 15
一般为 O(n^2)

如果最大值总在中间附近，递归更均衡，表现会接近 O(n log n)。但最坏情况不能忽略。

五、单调栈优化的直觉

最大二叉树也可以看成每个元素找到左右两侧第一个比它大的元素，较小的那个大元素会成为它的父节点。单调递减栈可以在线性时间维护这些关系。新元素到来时，比它小的栈顶会被弹出，成为它的左孩子；如果栈里还有更大的元素，新元素会成为栈顶的右孩子。

保持栈从底到顶递减
遇到更大元素，弹出的最后一个较小元素接到它左边
当前元素再接到更大栈顶的右边

这个优化不一定要现场完整写出，但能体现深度。

六、常见误区与追问

误区：把最大二叉树当成 BST。 它不满足左小右大规则，根来自区间最大值。
误区：认为直接分治一定 O(n log n)。 找最大值如果每层线性扫，单调数组会退化到 O(n^2)。
误区：递归区间包含 maxIdx。 最大值已经作为根，左右递归要排除它。
追问：如何优化到 O(n)？ 用单调递减栈构造父子关系。
追问：数组有重复值怎么办？ 标准题通常元素唯一；有重复时要定义最大值选择规则。

这些问题考的是定义、复杂度和优化意识。

七、加强记忆

最大二叉树记成“最大值当根，左右区间递归”。它是按数组位置切分，不是按 BST 大小规则切分。朴素实现清晰但可能 O(n^2)，因为每层都扫描最大值；如果追求最优，用单调递减栈一次性建立父子关系。

简化版

详细版