本文共 1395 字，大约阅读时间需要 4 分钟。

class Solution {
   public:    int mctFromLeafValues(vector
   
    & arr) {
           int siz=arr.size();        if(!siz)            return 0;        vector
    
     
      > MAX(siz,vector
      
       (siz));        vector
       
        
         > dp(siz,vector
         
          (siz,0x3f3f3f3f)); for(int i=0;i
         
        
       
      
     
    
   

思路二：单调栈。这个有点难想，看了别人的题解才学到。

class Solution {
   public:    int mctFromLeafValues(vector
   
    & arr) {
           stack
    
      s;        int siz=arr.size(),ans=0;        for(int i=0;i
     
      =s.top()){
                   int tmp=s.top();                s.pop();                if(s.empty())                    ans+=tmp*arr[i];                else                    ans+=tmp*min(arr[i],s.top());             }            s.push(arr[i]);        }        while(s.size()>=2){
               int tmp=s.top();            s.pop();            ans+=tmp*s.top();        }        return ans;    }};
     
    
   

转载地址：https://blog.csdn.net/xiji333/article/details/107955045 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！