1130. Minimum Cost Tree From Leaf Values
Given an array arr of positive integers, consider all binary trees such that:
- Each node has either 0 or 2 children;
- The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
- The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively. Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.
Example
Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees. The first has non-leaf node sum 36, and the second has non-leaf node sum 32.
24 24
/ \ / \
12 4 6 8
/ \ / \
6 2 2 4
题意：这道题讲的就是考虑一个数组，其数组的值均是一个满足以下三个条件的树的叶子节点。 1. 每个 node 都有 0 个或者 2 个子孩子。 2. 数组的值和 tree 中序排序后叶子节点所对应。 3. 非叶子节点就等于左子树最大元素和右子树最大元素的乘积。 问，这些所有能组合出来的树里面，非叶子节点最小和是多少。
解法1：先来一个比较暴力的解法。记忆化搜索， 其实就是brute force。 遍历数组一遍， 分别把数组分成对应的两半，分别就递归进去计算。 把所有可能都算一遍。为了避免重复计算，我们可以用一个 map 来记录已经算过的区间。复杂度是填表的时间， 也就是 $o(n^3)$ 复杂度。
代码
class Solution {
public int[] helper(int[] arr, int start, int end, Map<String, int[]> map) {
if(map.containsKey(start + "-" + end)) return map.get(start + "-" + end);
if(start == end) return new int[]{0, arr[start]};
int ret = Integer.MAX_VALUE, largest = 0;
for(int i = start; i < end; i++) {
int[] left = helper(arr, start, i, map);
int[] right = helper(arr, i + 1, end, map);
int sum = left[1]*right[1] + left[0] + right[0];
if(ret > sum) {
ret = sum;
largest = Math.max(left[1], right[1]);
}
}
map.put(start + "-" + end, new int[]{ret, largest});
//System.out.println(ret + " " + largest);
return new int[]{ret, largest};
}
public int mctFromLeafValues(int[] arr) {
Map<String, int[]> map = new HashMap<>();
return helper(arr, 0, arr.length-1, map)[0];
}
}
解法2：贪心，因为每次非叶子节点的值都是来自于左右子树中较大的那个值。这样的话，我们应该把最小的值放在最深的地方，这样做可以减少大数的多次使用。 那么这一题就等价两两合并数值 $a$ 和 $b$. 合并他们的索需要的 cost 是 a*b, 问我们合并所有元素直到只剩一个元素的 cost 是多少。 注意合并完 $a$ 和 $b$， 我们可以将其中一个比较小的值舍弃。因为它以后再也不会用到。稍大的数一定会被 pick 而不是这个较小的数。 以这个角度来看的话，那么我们每次就找到最小的相邻两个数的乘积之后，将其中小的抛弃即可。直到只剩下一个元素。
代码
class Solution {
public int mctFromLeafValues(int[] arr) {
int ret = 0;
List<Integer> list = new ArrayList<>();
for(int i : arr) list.add(i);
while(list.size() != 1) {
int tmp = Integer.MAX_VALUE;
int index = 0, fst = 0, snd = 0;
for(int i = 0; i < list.size() - 1; i++) {
if(tmp > list.get(i) * list.get(i + 1)) {
tmp = list.get(i) * list.get(i + 1);
index = list.get(i) > list.get(i + 1) ? i + 1 : i;
fst = i;
snd = i + 1;
}
}
ret += list.get(fst) * list.get(snd);
list.remove(index);
}
return ret;
}
}
解法3：终于直击此summary的主题了，那就是用单调栈呃。 延续解法二的思路，我们没有必要从最小的 pair 开始找。对于任何一个 local minimal 我们都可以对其直接计算，并舍弃它。所以这个问题就转变成了找出左右比较大的值，取较小的值相乘。 所以是一个单调递减栈。 这也使得这道题的时间复杂度从 $O(n^3)$ 降到了 $O(n)$.
class Solution {
public int mctFromLeafValues(int[] arr) {
Stack<Integer> stack = new Stack<>();
int ret = 0;
for(int i = 0; i < arr.length; i++) {
while(!stack.isEmpty() && stack.peek() < arr[i]) {
int cur = stack.pop();
ret += cur * Math.min(stack.isEmpty() ? arr[i] : stack.peek(), arr[i]);
}
stack.push(arr[i]);
}
while(stack.size() > 1) {
ret += stack.pop() * stack.peek();
}
return ret;
}
}