[Leetcode 42, Hard] Trapping Rain Water

Problem:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 

Given 

[0,1,0,2,1,0,1,3,2,1,2,1]

, return 

6

.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Analysis:

Solutions:

C++:

int trap(vector<int>& height) {
        if(height.empty())
            return 0;
            
        stack<int> end_point_stack;
        for(int i = 0; i < height.size(); ++i) {
            if(height[i] == 0)
                continue;
            else {
                if((i == 0 && height[i] > height[i + 1]) || (i == height.size() - 1 && height[i] > height[i - 1])
                   || (height[i] >= height[i + 1] && height[i] > height[i - 1]) 
                   || (height[i] > height[i + 1] && height[i] >= height[i - 1])) 
                    {
                        if(end_point_stack.size() <= 1 || height[end_point_stack.top()] >= height[i])
                            end_point_stack.push(i);
                        else {
                            while(end_point_stack.size() > 1) {
                                int top_height = end_point_stack.top();
                                end_point_stack.pop();
                                if(height[top_height] > height[end_point_stack.top()] || height[top_height] >= height[i]) {
                                    end_point_stack.push(top_height);
                                    end_point_stack.push(i);
                                    break;
                                }
                            }
                            
                            if(end_point_stack.size() == 1)
                                end_point_stack.push(i);
                        }
                    }
            }
        }
        
        if(end_point_stack.empty())
            return 0;
        
        vector<int> index;
        while(!end_point_stack.empty()) {
            index.insert(index.begin(), end_point_stack.top());
            end_point_stack.pop();
        }
        
        int r_sum = 0;
        for(int i = 0; i < index.size() - 1; ++i) {
            int h = min(height[index[i]], height[index[i + 1]]);
            int part_sum = 0;
            for(int j = index[i] + 1; j <  index[i + 1]; ++j) {
                if(height[j] > h)
                    continue;
                part_sum += h - height[j];
            }
            r_sum += part_sum;
        }
        
        return r_sum;
    }
           

Java :

Python: