search

cjql / algorithm

https://cjql.github.io/algorithm/
1 stars 1 forks source link

LeetCode_Dynamic: https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/submissions/ #6

Open cjql opened 4 years ago

cjql commented 4 years ago

C++

Java

Python

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        res = 0
        stack = [float('inf')]
        for a in arr:
            while stack[-1] <= a:
                mid = stack.pop()
                res += mid * min(stack[-1], a)
            stack.append(a)
        while len(stack)  >2:
            res += stack.pop() * stack[-1]
        return res

C

C

JavaScript

Ruby

Swift

Go

Scala

Kotlin

Rust

PHP