第一反应是 dp, 的确 dp 可以做, 不过不仅时间复杂度高, 而且写起来也有点麻烦, 更好的做法竟然只是简单的贪心, lee215 的题解
const mctFromLeafValues = function (arr) {
const al = arr.length;
let res = 0;
const s = [Number.MAX_SAFE_INTEGER];
for (const a of arr) {
while (s[s.length - 1] <= a) {
let m = s[s.length - 1];
s.pop();
res += m * Math.min(s[s.length - 1], a);
}
s.push(a);
}
for (let i = 2; i < s.length; i++) {
res += s[i] * s[i - 1];
}
// console.log(res);
return res;
};