42. After the rain

Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.

Topic describes

Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.

Example 1

Enter: height = [0.1.0.2.1.0.1.3.2.1.2.1] output:6Explanation: The above is made up of arrays [0.1.0.2.1.0.1.3.2.1.2.1] represents the height diagram, in this case, can be connected61 unit of rain (blue indicates rain).Copy the code

Thought analysis

Pay attention to the law of water accumulation. From left to right, water accumulation will occur only when the value of the left boundary is less than or equal to the value of the right boundary. Meanwhile, pay attention to this part.

For 1 on the left, 1 on the right, you can get 1 unit of rain, and this calculation is actually

But for 2 and 3, when we calculate

(IDx right 1− IDX left 1−1)(IDx_ {right 1} -IDx_ {left 1} -1)(IDx right 1− IDx left 1−1) This makes us ignore the fact that there are three elements needed to catch rain: the left edge, the bottom edge, and the right edge.

The specific implementation

int trap(vector<int>& height) {
        int length = height.size(a);int ret = 0;
        vector<int> arr(length);
        stack<int> stk;
        for(int i = 0; i < length; i++){
            while(! stk.empty() && height[stk.top()] <= height[i]) {
                int tmp = stk.top(a); stk.pop(a);if(stk.empty()) {break;
                }
                int left = stk.top(a); ret += ((i - left -1) * (min(height[left], height[i]) - height[tmp]));
                // arr[tmp] = i;
            }
            stk.push(i);
        }
        // for(int i = 0; i < length; i++){
        // int t = arr[i] - i - 1;
        // if (t > 0){
        // ret += t;
        / /}
        // }
        return ret;
    }
Copy the code