Approach 1: Monotonic Stack

The monotonic stack method offers a linear time complexity solution, O(n), with O(n) space complexity. While it may appear more complex to implement than a recursive approach, it provides superior performance in large-scale scenarios. The algorithm iterates through the input array, utilizing a stack to maintain nodes and construct the tree based on relative values.

Logic:

1. Initialize an empty stack to hold TreeNode objects.
2. Iterate through each number in the input array:
   • Create a tree node for the current number.
   • While the stack is not empty and the current value is greater than the value of the node at the stack's top, pop the stack. The popped node is assigned as the left child of the current node.
   • If the stack is not empty after popping, the current node becomes the right child of the node now at the top of the stack.
   • Push the current node onto the stack.
3. After processing all elements, the bottom element of the stack will be the root of the maximum binary tree.

Implementation:

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        
        int len = nums.length;
        TreeNode[] nodeStack = new TreeNode[len];
        int stackTop = -1;

        for (int i = 0; i < len; i++) {
            TreeNode currentNode = new TreeNode(nums[i]);
            
            // Pop smaller elements to become the left child of current node
            while (stackTop >= 0 && nums[i] > nodeStack[stackTop].val) {
                currentNode.left = nodeStack[stackTop--];
            }
            
            // If stack is not empty, current node becomes right child of stack top
            if (stackTop >= 0) {
                nodeStack[stackTop].right = currentNode;
            }
            
            // Push current node onto stack
            nodeStack[++stackTop] = currentNode;
        }
        
        return nodeStack[0];
    }
}

Approach 2: Recursive Construction

This method follows a straightforward divide-and-conquer strategy. It typically has a time complexity of O(n²) due to the scan for the maximum value in each subarray, with a space complexity of O(n) for the recursion stack.

Logic:

1. Identify the maximum value in the current array segment. This value serves as the root of the current subtree.
2. The index of this maximum value divides the array into left and right subarrays.
3. Recursively build the left subtree using the left subarray.
4. Recursively build the right subtree using the right subarray.
5. Base cases: if the segment is empty, return null; if the segment contains one element, return a node for that element.

Implementation:

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return buildSubtree(nums, 0, nums.length - 1);
    }

    private TreeNode buildSubtree(int[] nums, int leftBound, int rightBound) {
        if (leftBound > rightBound) {
            return null;
        }
        if (leftBound == rightBound) {
            return new TreeNode(nums[leftBound]);
        }

        // Find index of the maximum element in the current range
        int maxIndex = leftBound;
        for (int i = leftBound + 1; i <= rightBound; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }

        TreeNode rootNode = new TreeNode(nums[maxIndex]);

        // Recursively construct left and right subtrees
        rootNode.left = buildSubtree(nums, leftBound, maxIndex - 1);
        rootNode.right = buildSubtree(nums, maxIndex + 1, rightBound);

        return rootNode;
    }
}