Very straight forward solution with time O(N) and space O(1) in C++


  • 0
    L
    class Solution {
    public:
        // the idea of this alg is that 
        // the final result would fall into the following 3 situations
        // 1) monotonically non-decrease, e.g. [1,2,2,3,3,4]
        // 2) monotonically non-increase, e.g. [4,3,3,2,2,1]
        // 3) (1) + [maxHeight] + (2), e.g. [1,2,2,3,3,4,4,4,3,3,2,2,1]
        // time: O(N), space: O(1)
        int trap(vector<int>& h) {
            if(h.empty() == true) return 0;
            int maxh = *max_element(h.begin(),h.end());
            
            // 1st pass, monotonically non-decreasing from beginning to max_height
            int w = 0;
            int i; // index 
            for(i = 0; i<h.size(); i++) {
                if(h[i]==maxh) break; 
                if(i==0) continue; 
                if(h[i]<h[i-1]) {
                    w += h[i-1] - h[i]; // water amount
                    h[i] = h[i-1]; // increase 
                }
            }
            
            // 2nd pass, monotonically non-increasing from max_height to the end
            for(int j = h.size()-1; j>i; j--) {
                if(h[j]>h[j-1]) {
                    w += h[j]-h[j-1];
                    h[j-1] = h[j];
                }
            }
            return w;
        }
    };
    

Log in to reply
 

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