class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
}
};
1130. 叶值的最小代价生成树
给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：
arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
示例：
输入：arr = [6,2,4]
输出：32
解释：
有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。
24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4
提示：
2 <= arr.length <= 401 <= arr[i] <= 152^31。原站题解
javascript 解法, 执行用时: 80 ms, 内存消耗: 44.6 MB, 提交时间: 2022-11-28 14:33:33
/**
* @param {number[]} arr
* @return {number}
*/
/**
* dp[i][j] 表示将 arr[i...j] 合并之后所得的最小乘积之和。
* dp[0][len] 就是最终答案。
*/
var mctFromLeafValues = function(arr) {
const n = arr.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));
const maxVal = new Array(n).fill(0).map(() => new Array(n).fill(0));
for(let i = 0; i < n; i++) {
maxVal[i][i] = arr[i];
for(let j = i + 1; j < n; j++) {
maxVal[i][j] = Math.max(maxVal[i][j-1], arr[j]);
}
}
for(let len = 1; len < n; len++) {
for(let i = 0; i + len < n; i++) {
dp[i][i+len] = Number.MAX_SAFE_INTEGER;
for(let k = i; k < i + len; k++) {
dp[i][i+len] = Math.min(dp[i][i+len], dp[i][k] + dp[k+1][i+len] + maxVal[i][k] * maxVal[k+1][i+len]);
}
}
}
return dp[0][n-1];
};
javascript 解法, 执行用时: 52 ms, 内存消耗: 41.1 MB, 提交时间: 2022-11-28 14:32:42
/**
* @param {number[]} arr
* @return {number}
*/
var mctFromLeafValues = function(arr) {
const n = arr.length;
const stack = [];
let res = 0;
for(let i = 0; i < n; i++) {
while(stack.length && (stack[stack.length-1] <= arr[i] || i === n-1)) {
const bottom = stack.pop();
if(stack.length) {
res += Math.min(stack[stack.length-1], arr[i]) * bottom;
} else {
res += bottom * arr[i];
}
arr[i] = Math.max(bottom, arr[i]);
}
stack.push(arr[i]);
}
return res;
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 8 MB, 提交时间: 2022-11-28 14:31:59
class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
int ans=0,pos=0;
while(arr.size()>1)
{
int Min=INT_MAX;
for(int i=0;i<arr.size()-1;++i)
{
if(Min>arr[i]*arr[i+1])//找到最小的两个值
{
Min=arr[i]*arr[i+1];
pos=arr[i]<arr[i+1]?i:i+1;
}
}
ans+=Min;
arr.erase(arr.begin()+pos);//删去其中最小的一个
}
return ans;
}
};
python3 解法, 执行用时: 36 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-28 14:31:19
class Solution:
def mctFromLeafValues(self, A: List[int]) -> int:
res, n = 0, len(A)
stack = [float('inf')]
for a in A:
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
python3 解法, 执行用时: 128 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-28 14:30:54
class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
n = len(arr)
# 初始值设为最大
dp = [[float('inf') for _ in range(n)] for _ in range(n)]
# 初始区间查询最大值设为0
maxval = [[0 for _ in range(n)] for _ in range(n)]
# 求区间[i, j]中最大元素
for i in range(n):
for j in range(i, n):
maxval[i][j] = max(arr[i:j + 1])
# 叶子结点不参与计算
for i in range(n):
dp[i][i] = 0
# 枚举区间长度
for l in range(1, n):
# 枚举区间起始点
for s in range(n - l):
# 枚举划分两棵子树
for k in range(s, s + l):
dp[s][s + l] = min(dp[s][s + l], dp[s][k] + dp[k + 1][s + l] + maxval[s][k] * maxval[k + 1][s + l])
return dp[0][n - 1]
java 解法, 执行用时: 1 ms, 内存消耗: 39.2 MB, 提交时间: 2022-11-28 14:29:43
class Solution {
public int mctFromLeafValues(int[] arr) {
Stack<Integer> st = new Stack();
st.push(Integer.MAX_VALUE);
int mct = 0;
for (int i = 0; i < arr.length; i++) {
while (arr[i] >= st.peek()) {
mct += st.pop() * Math.min(st.peek(), arr[i]);
}
st.push(arr[i]);
}
while (st.size() > 2) {
mct += st.pop() * st.peek();
}
return mct;
}
}