1130. 叶值的最小代价生成树

ITCharge大约 4 分钟

---

1130. 叶值的最小代价生成树

标签：栈、贪心、数组、动态规划、单调栈
难度：中等

题目链接

1130. 叶值的最小代价生成树 - 力扣

题目大意

描述：给定一个正整数数组 $arr$ 。考虑所有满足以下条件的二叉树：

每个节点要么有 $0$ 个子节点（叶子节点），要么有 $2$ 个子节点（非叶子节点）。
数组 $arr$ 中的值与树的中序遍历中每个叶节点的值一一对应（即叶子节点从左到右就是数组的顺序）。
每个非叶子节点的值 = 其左子树中叶节点的最大值 × 其右子树中叶节点的最大值。

要求：在所有这样的二叉树中，返回每个非叶子节点的值的最小可能总和。

说明：

$2 \le arr.length \le 40$ 。
$1 \le arr[i] \le 15$ 。
答案保证是一个 $32$ 位带符号整数，即小于 $2^{31}$ 。

示例：

示例 1：

输入：arr = [6,2,4]
输出：32
解释：有两种可能的树，第一种的非叶节点的总和为 36 ，第二种非叶节点的总和为 32 。

示例 2：

输入：arr = [4,11]
输出：44

解题思路

思路 1：单调栈 + 贪心

核心思路：如果一个数字很小，我们希望它尽早被"吞并"（即和相邻的数字合并），因为合并后它就不再是所在组的最大值了，不会参与后续更贵的乘法。如果一个数字很大，我们希望它尽量晚参与合并，减少它参与乘法的次数。

单调递减栈的作用：用栈来维护一个「从栈底到栈顶单调递减」的序列，也就是栈里的元素从下到上越来越小。

遍历数组时，如果当前数字比栈顶元素大，说明栈顶这个小数字的右边出现了一个更大的数字。这时候小数字就要做决定了——它应该和左边还是右边的数字合并？答案是：和左右两边中更小的那个合并（因为合并成本是两个组的最大值相乘，和更小的合并成本更低）。

拆解步骤：

在栈底放一个哨兵：往栈里先放一个无穷大 float('inf')，这样第一个元素比较时不会出错。
从左到右遍历每个数字：
- 只要当前数字 >= 栈顶元素（说明栈顶这个小数字右边来了一个更大的）：
  - 弹出栈顶元素 mid，它就是当前要处理的小数字
  - 它的左邻居是新的栈顶（栈里在它下面的那个数），右邻居是当前正在遍历的数字
  - 合并成本 = mid × min(左邻居, 右邻居)，累加到答案
  - 继续检查新的栈顶，直到栈顶比当前数字大
- 把当前数字压入栈中
处理栈里剩下的元素：遍历完后，栈里剩下的元素是从大到小排列的（栈顶最小）。依次弹出并合并即可——每个弹出的元素和它下面的那个元素合并。

为什么这个贪心是对的？ 每次合并时，我们都在确保当前最小的数字用尽可能小的成本被"吸收"掉——它和左右两边中较小的那个合并，成本最低。这样一步步把小的都处理掉，最终得到的就是最小总成本。

思路 1：代码

class Solution:
    def mctFromLeafValues(self, arr: List[int]) -> int:
        # 在栈底放一个无穷大，方便处理边界情况
        stack = [float('inf')]
        ans = 0

        for num in arr:
            # 当前数字比栈顶大时，说明栈顶元素的右边出现了更大的数
            # 栈顶这个小数字需要被处理掉
            while stack[-1] <= num:
                mid = stack.pop()  # 弹出这个小数字
                # 它和左右两边中较小的那个合并（左 = stack[-1], 右 = num）
                ans += mid * min(stack[-1], num)

            # 当前数字入栈
            stack.append(num)

        # 处理栈里剩下的元素，从栈顶开始依次向下合并
        while len(stack) > 2:
            mid = stack.pop()
            ans += mid * stack[-1]

        return ans

思路 1：复杂度分析

时间复杂度： $O(n)$ 。用人话说就是：每个数字最多入栈一次、出栈一次，总共处理 $n$ 个元素，所以是线性时间。
空间复杂度： $O(n)$ 。最坏情况下栈里需要存 $n$ 个元素。