leetcode叶值的最小代价生成树

系统管理员 2022-09-03 14:30 131阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路：

1.  给出的序列是中序遍历的叶子节点，也就是每个值都只能和其左边或者右边结合成左右子树的叶子节点。`[1,2,3,4]`，比如2只能和1或者3组成左右子树的叶子节点
2.  构造的树有点类似于哈夫曼树，就是希望最小的叶子节点处于最下面，即计算次数最多，从底向上就是先进行计算的，**需要找到当前叶子节点极小值**。
3.  所以入栈的都是比栈顶小的值，只有找到比栈顶大的值，栈顶才是找到的极小值。
4.  **单调递减栈**
5.  当找到栈顶极小值时，栈顶可以和左右两边的最小值构成左右子树节点，`stack[top-1]和arr[i]`中的最小值
6.  在栈顶部加一个最大值，可以不用考虑top-1是否出界
7.  如果遍历完整个数组，栈中还有值，那么就是单调递减的序列，每一个栈顶都是当前极小值，所以就可以直接进行计算。

#include<stdio.h>
    #include<string.h>
    #define max(a,b) ((a)>(b)?a:b)
    #define min(a,b) ((a)<(b)?a:b)
    //单调递减栈
    int mctFromLeafValues(int* arr, int arrSize){ 
        int i=0,top=0;
        int res = 0;
        int stack[arrSize+1];
        stack[0] = 16;
        while (i<arrSize)
        { 
           if (top<1)
           { 
               stack[++top]=arr[i++];
           }
           else { 
               //单调递减，当前最小，入栈
               if(arr[i]<stack[top]){ 
                   stack[++top] = arr[i++];
               }
               else{ 
                   res = res + stack[top]*min(stack[top-1],arr[i]);
                   top--;
               }
           } 
        }
        while (top>1)
        { 
            res = res + stack[top]*stack[top-1];
            top--;
        }
        return res;
        
    }
    
    int main(){ 
        int arr[] = { 4,3,2,1};
        int re = mctFromLeafValues(arr,4);
        printf("re = %d\n",re);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/ae2b64a054624d56ad50fa55a8b03ed0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20220829/73f0662e8d354e9c95246ba967a35ab9.png