This is why I *LOVE* C++11! (O(n) solution with heavy use of STL and no loops)


  • 0
    C
    //Divide the input into two sections of (kinda) monotonically increasing sequences
    //then do a left fold from the lhs->max and a right fold from max<-rhs
    class Solution {
        typedef pair<int, int> t_ACCNMAX; //(sum so far, maximum-height-so-far)
    public:
        int trap(vector<int>& height) {
            if (height.size() == 0 || height.size() == 1) return 0;
            
            int max = std::accumulate(height.begin(), height.end(), std::numeric_limits<int>::min(), 
                [] (const int& acc, const int& val) -> int {
                return (acc > val ? acc : val);
            });
            auto maxrit = std::find(height.rbegin(), height.rend(), max);
            auto maxfit = (maxrit + 1).base();
            
            std::function<t_ACCNMAX (t_ACCNMAX, int)> foldFunc = [] (t_ACCNMAX summaxht, int ht) -> t_ACCNMAX {
                int maxht   = summaxht.second;
                int sumsofar= summaxht.first;
                int newsum = maxht > ht ? (maxht - ht) : 0;
                return std::make_pair(sumsofar + newsum, ht > maxht ? ht : maxht);
            };
            
            t_ACCNMAX accumulator = std::make_pair(0, 0);
            t_ACCNMAX lhsMono = std::accumulate(height.begin(),  maxfit, accumulator, foldFunc);
            t_ACCNMAX rhsMono = std::accumulate(height.rbegin(), maxrit, accumulator, foldFunc);
            
            return (lhsMono.first + rhsMono.first);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.