nikunjsoni

1130

Mar 22nd, 2021
66
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int min(int a, int b){
  4.         return (a < b) ? a:  b;
  5.     }
  6.    
  7.     int mctFromLeafValues(vector<int>& arr) {
  8.         int res = 0;
  9.         vector<int> stk = {INT_MAX};
  10.         for(int a:arr){
  11.             while(stk.back() <= a){
  12.                 int last_max = stk.back();
  13.                 stk.pop_back();
  14.                 res += last_max * min(stk.back(), a);
  15.             }
  16.             stk.push_back(a);
  17.         }
  18.         for(int i=2; i<stk.size(); i++)
  19.             res += stk[i]*stk[i-1];
  20.         return res;
  21.     }
  22. };
RAW Paste Data