给你一个正整数数组 arr,考虑所有满足以下条件的二叉树:
每个节点都有 0 个或是 2 个子节点。
数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。
每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
在所有这样的二叉树中,返回每个非叶节点的值的最小可能总和。
1. 贪心+单调栈
该问题不适合列举所有可能得二叉树进行判断
通过试图贪心构造最优的二叉树
观察到节点的度只能为0或2,最终非叶子节点数为n-1
所以必然会进行n-1次合并,优先对小的进行合并
这里使用单调栈
class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
stack<int> s;
int n = arr.size();
int res = 0;
//单调栈,当前数大于栈顶时,把栈前面所有小的数合并掉
for(int i=0;i<n;i++){//遍历所有数
if(!s.empty()&&arr[i]>=s.top()){
int cur = s.top(); s.pop();//把前面小于等于arr[i]的数全部合并掉
while(!s.empty()&&arr[i]>=s.top()){
res+=cur*s.top();//合并
cur = s.top(); s.pop();
}
res+=cur*arr[i];//将arr[i]与最终结果合并
}
s.push(arr[i]);
}
int cur = s.top();s.pop();
while(!s.empty()){
res+=cur*s.top();
cur =s.top(); s.pop();
}
return res;
}
};
标签:arr,cur,int,叶值,top,节点,res,代价,LeetCode
From: https://www.cnblogs.com/929code/p/17447649.html