C++刷LeetCode（1130. 叶值的最小代价生成树）【递减栈】【数学】

糖逗

题目描述：

1. 给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：
   
2. 
   
3. 每个节点都有 0 个或是 2 个子节点。
   
4. 数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）
   
5. 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。
   
6. 在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。
   
7. 
   
8.  
   
9. 
   
10. 示例：
    
11. 
    
12. 输入：arr = [6,2,4]
    
13. 输出：32
    
14. 解释：
    
15. 有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。
    
16. 
    
17.     24            24
    
18.    /  \          /  \
    
19.   12   4        6    8
    
20. /  \               / \
    
21. 6    2             2   4
    
22.  
    
23. 
    
24. 提示：
    
25. 
    
26. 2 <= arr.length <= 40
    
27. 1 <= arr[i] <= 15
    
28. 答案保证是一个 32 位带符号整数，即小于&#160;2^31。
    
29. 
    
30. 来源：力扣（LeetCode）
    
31. 链接：https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values
    
32. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int mctFromLeafValues(vector<int>& arr) {
   
4.         int res = 0;
   
5.         stack<int>store;
   
6.         store.push(INT_MAX);
   
7.         for(auto cha : arr){
   
8.             while(cha > store.top()){
   
9.                 int temp = store.top();
   
10.                 store.pop();
    
11.                 res += temp * min(store.top(), cha);
    
12.             }
    
13.             store.push(cha);
    
14.         }
    
15.         while(store.size() > 2){
    
16.             int temp = store.top();
    
17.             store.pop();
    
18.             res += temp * store.top();
    
19.         }
    
20.         return res;
    
21.     }
    
22. };

复制代码

参考链接：https://leetcode-cn.com/problems ... zhan-by-crossing-2/