problem:1130. 叶值的最小代价生成树

题目转换：
给你一个长度为n的数组，你可以合并相邻的数，合并后的数为两者较大的数，代价为这两个数的积，求合并到无法合并为止，所花费代价总和的最小值。

思路：搬运自leetcode

Accode：

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
        int len = arr.size();
        stack<int> sta;
        int ans = 0;
        for(int i=0;i<len;i++){
            while(sta.size() && arr[i]>sta.top()){
                int top = sta.top();
                sta.pop();
                if(sta.size()){
                    if(sta.top()>arr[i]){
                        ans+=arr[i]*top;
                    }
                    else ans+=top*sta.top();
                }
                else ans+=top*arr[i];
            }
            sta.push(arr[i]);
        }
        while(sta.size()>1){
            int top = sta.top();
            sta.pop();
            if(sta.size())ans+=sta.top()*top;
        }
        return ans;
    }
};

时间复杂度：$o(n)$