1130. Minimum Cost Tree From Leaf Values (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def mctFromLeafValues(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        # monostack
        result = 0
        monostack = [float("inf")]
        for num in arr:
            while num >= monostack[-1]:
                m = monostack.pop()
                result += m * min(monostack[-1], num)
            monostack.append(num)
        while len(monostack) > 2:
            result += monostack.pop() * monostack[-1]
        return result
    
        # greedy
        result = 0
        while len(arr) > 1:
            i = arr.index(min(arr))
            result += min(arr[i - 1 : i] + arr[i + 1 : i + 2]) * arr.pop(i)
        return result