1130. Minimum Cost Tree From Leaf Values

這題真的是鬼, 這估計給我想多年都想不出來

李哥真的很猛

這邊的概率就是先挑一個local min(A), 然後, 從他的兩側去找出除了(A)以外的最小值, 然後作乘積, Ａ就可以丟掉了

這邊用到stack的技巧, 非常精彩

class Solution {
public:
    int mctFromLeafValues(vector<int>& arr) {
       
        int res = 0;
        vector<int> vec = {INT_MAX};
        for(auto a : arr){
            while(vec.back() <= a){
                int mid = vec.back();
                vec.pop_back();
                res += mid * min(vec.back(), a);
            }
            vec.push_back(a);
        }
        for(int i = 2; i < vec.size();i++){
            res += vec[i] * vec[i - 1];
        }
        return res;
    }
};