LC 0654 [M] Maximum Binary Tree - ALawliet/algorithms GitHub Wiki

we can use a decreasing monotonic stack to find the next greater element to the left and the right

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        # if not nums:
            # return None
        
        dec_stack = []  #build a decreasing monotonic stack
        for val in nums:
            node = TreeNode(val)
            
            # next greatest element to the left
            lastpop = None
            while dec_stack and val > dec_stack[-1].val:  #popping process
                lastpop = dec_stack.pop()
            node.left = lastpop
            
            # next greatest element to the right
            if dec_stack:
                dec_stack[-1].right = node
            dec_stack.append(node)
            
        return dec_stack[0]