递归

最容易想到，采用先序遍历。

1.遍历数组，找出当前区间的最大值；

2.使用该最大值作为根节点；

3.对数组的左半部分和右半部分递归调用构建最大二叉树。

这种方式是标准的 分治法，每次递归都需要遍历当前区间，找到最大值。因此，时间复杂度是 O(n^2)，因为每一层递归都会遍历一遍数组，且递归的深度为 n。

一定要坚持循环不变量，这里的递归区间都选择左闭右开区间

代码

class Solution {
public:
//本题和从中序后续构造二叉树不同，本题每次递归只用使用一个数组， 所以只需要left和right
    TreeNode* buildTree(vector<int>& nums,int left,int right){//[left,right)区间
        //先序遍历 递归
        if(left >= right)return nullptr;

        //遍历找到最大值和索引
        int maxNum = -1,maxId = 0;
        for(int i = left;i<right;i++){
            if(nums[i] > maxNum){
                maxNum = nums[i];
                maxId =i;
            }
        }
        TreeNode* root = new TreeNode(maxNum);

        root->left = buildTree(nums,left,maxId);
        root->right = buildTree(nums,maxId+1,right);    

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
	return buildTree(nums,0,nums.size());
    }
};

单调栈

单调栈是一个辅助数据结构，用来维护某些元素的顺序（例如，递增或递减顺序）。在这道题中，我们可以利用单调栈来帮助我们快速找到每个元素在构建最大二叉树时的 父子关系

为什么单调栈能够优化？

单调栈能优化这个问题的关键在于它能够快速找到每个元素的 最大值 以及该值在当前区间内的位置，而不需要每次都遍历整个区间。它通过维护一个单调栈来做到这一点，从而提高时间效率。时间复杂度O(N)。

步骤：

单调栈的维护：我们从左到右扫描数组，对于每个新元素 nums[i]：

• 如果栈顶的元素比 nums[i] 小，栈顶元素出栈，作为当前元素的左子树，直到栈顶元素比 nums[i] 大或栈为空。
• 如果栈顶元素比nums[i]大，当前元素入栈，作为栈顶元素的右子树
• 如果栈为空，当前元素直接入栈，更新要返回的root节点为当前元素节点（此时当前元素一定是局部的最大值）

代码

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // return buildTree(nums,0,nums.size());
        stack<TreeNode*> st;
        TreeNode* root = nullptr;

        for(int num:nums){
            TreeNode* node = new TreeNode(num);
            //1.如果栈非空，且栈顶值小于当前值，出栈作为左子树
            while(!st.empty() && st.top()->val < num){
                node->left = st.top();
                st.pop();
            }
            //2.如果栈非空，且栈顶值大于当前值，入栈作为右子树
            if(!st.empty()){
                st.top()->right = node;
                st.push(node);
            }else{//3.栈为空，直接入栈；
                root = node;
                st.push(node);
            }
        }

        return root;
    }