Leetcode 42. rainwater connection

Rainwater collection

Given n Nonnegative integers indicate that each width is 1 Height map of columns of , Calculate columns arranged in this way , How much rain can be received after rain .

Example 1：

Input ： height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output ： 6
explain ： Above is an array of [0,1,0,2,1,0,1,3,2,1,2,1] Height map of representation , under these circumstances , Can connect 6 Units of rain （ The blue part indicates rain ）.

Example 2：

Input ： height = [4,2,0,3,2,5]
Output ： 9

Tips ：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

https://leetcode-cn.com/problems/trapping-rain-water

This position can be installed at most 1 Geshui . The maximum height on its left is l_max = 2 grid , Its maximum height on the right is r_max = 3 grid , Therefore, the maximum height of water at this position is min(l_max,r_max) = 2, And because of the height of this position height[i] = 1, So you can install at most min(l_max,r_max) - height[i] = 2 - 1 = 1 Geshui .

class Solution {
    
public:
    int trap(vector<int>& height) {
    
        int i, len = height.size(), l_max, r_max, sum = 0;
        for(i=1;i<len-1;i++){
    
            l_max = 0;
            r_max = 0;
            // Find the tallest post on the left 
            for(int j=i; j>=0; j--)
                l_max = max(l_max, height[j]);
            // Find the tallest post on the right 
            for(int j=i; j<len; j++)
                r_max = max(r_max, height[j]);
            sum += min(l_max, r_max) - height[i];
        }
        return sum;
    }
};

Then comes the optimization of the code , Because this code will time out .
Dynamic programming
Store in advance the maximum height of all columns at each position and the maximum height of all right columns .
You can open two arrays l_max and r_max To serve as a memo .
l_max[i] It means the first one i Elements in position , The height of the tallest column on its left
r_max[i] It means the first one i Elements in position , The height of the tallest column on its right

class Solution {
    
public:
	int trap(vector<int>& height) {
    
        // Judge height Is it empty , That is to say height = []
        if(height.empty()) return 0;
		int i, len = height.size(), sum = 0;
		vector<int> l_max(len), r_max(len); // Create a memo 
        // initialization 
		l_max[0] = height[0];
		r_max[len - 1] = height[len - 1];
        // Calculate from left to right l_max[i]
		for (i = 1; i<len; i++)
			l_max[i] = max(l_max[i - 1], height[i]);
        // Calculate from right to left r_max[i]
		for (i = len - 2; i >= 0; i--)
			r_max[i] = max(r_max[i + 1], height[i]);
        // Calculate the total amount of rainwater that can be received 
		for (i = 1; i<len - 1; i++)
			sum += min(l_max[i], r_max[i]) - height[i];
		return sum;
	}
};

Dynamic programming complexity analysis ：

• Time complexity O(n)
• Spatial complexity O(n)

Monotonic stack

class Solution {
    
public:
	int trap(vector<int>& height)
	{
    
		int ans = 0, current = 0;
		stack<int> s;
		while (current < height.size()) {
    
			while (!s.empty() && height[current] > height[s.top()]) {
    
				int top = s.top();
				s.pop();
				// Press out the stack before , The stack may be empty  
				if (s.empty())
					break;
				int distance = current - s.top() - 1; // Be careful ①: It can't be current - top
				int bounded_height = min(height[current], height[s.top()]) - height[top];
				ans += distance * bounded_height;
			}
			s.push(current++);
		}
		return ans;
	}
};

for instance

Input ： [3,0,2,1,0,2,3]
Output ： 10

Double pointer solution
Because I only care min(l_max, r_max), if l_max < r_max, Then the highest height of the water is determined by l_max To decide , as for r_max Whether it is left The highest pillar to the right of the pointer , Is not important , It is important to height[i] The water that can hold is only with l_max of .

LeetCode Official video explanation ：
https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/

class Solution {
    
public:
	int trap(vector<int>& height)
	{
    
        if(height.empty())
            return 0;
        int len = height.size();
        int left = 0, right = len - 1;
        int sum = 0;
        int l_max = height[0];
        int r_max = height[len-1];
        while(left<=right){
    
            l_max = max(l_max, height[left]);
            r_max = max(r_max, height[right]);

            if(l_max < r_max){
    
                    sum += l_max - height[left];
                    left++;     
            }
            else{
    
                    sum += r_max - height[right];
                    right--;     
            }

        }
		return sum;
	}
};