👉 “Offer to drive, dig friends to accept! I am participating in the 2022 Spring Recruit Punch card activity click to see the details of the activity.

42. After the rain

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:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6Copy the code

Example 2:

Height = [4,2,0,3,2,5Copy the code

Tip:

  • n == height.length
  • 0 <= n <= 3 * 10^4
  • 0 <= height[i] <= 10^5

Idea 1: Violence

For the ith pillar, the highest value of the left pillar is L and the highest value of the right pillar is R, so the rainfall volume that the ith pillar can reach is min(L,r) -height [I].

Walk through all columns, calculate the amount of rain water each column can receive, and sum.

C + + version 
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0,n = height.size(a);for(int i = 1; i < n - 1; i++){
            int l = 0, r = 0;
            for(int j = i; j >= 0; j--){
                l = max(l,height[j]);
            }
            for(int j = i; j < n; j++){
                r = max(r,height[j]);
            }
            ans += min(l,r) - height[i];
        }
        returnans; }};Copy the code

Train of thought 2: Optimize train of thought 1, preprocess the height value of the highest column on the left and right sides of the current column.

C + + version 
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(),ans = 0;
        if(n == 0) return 0;
        vector<int> l(n,0).r(n,0);
        l[0] = height[0];
        for(int i = 1; i < n; i++){
            l[i] = max(height[i],l[i - 1]);
        }
        r[n - 1] = height[n - 1];
        for(int i = n - 2; i >= 0; i--){
            r[i] = max(height[i],r[i + 1]);
        }
        for(int i = 1; i < n - 1; i++){
            ans += min(l[i],r[i]) - height[i];
        }
        returnans; }};Copy the code

Idea 3: Dual Pointers

  • From idea 2, as long as r_max > l_max, the height of the water will be determined by L_max, as long as r_max < l_max, the height of the water will be determined by R_max;
  • So if there are higher bars on one side (right), the height of the water depends on the height from left to right, and vice versa.
C + + version 
class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0,r = height.size() - 1,ans = 0;
        int l_mx = 0,r_mx = 0;
        while(l < r){
            if(height[l] < height[r]){
                if(height[l] > l_mx) l_mx = height[l];
                else ans += l_mx - height[l];
                l++;
            }else{
                if(height[r] > r_mx) r_mx = height[r];
                elseans += r_mx - height[r]; r--; }}returnans; }};Copy the code

Idea four: monotonous stack

  • Maintain a monotone descending stack. When some elements need to pop up, it means that a depression has been formed. At this time, calculate the height of the current depression and add it to the result.
C + + version 
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, n = height.size(a);if(n == 0) return 0;
        stack<int> st;
        for(int i = 0; i < n; i++){
            while(st.size(a)and height[st.top()] < height[i]){
                int cur = st.top(a); st.pop(a);if(st.size()) ans += (i - st.top() - 1) * (min(height[i],height[st.top()]) - height[cur]);   
            }
            st.push(i);
        }
        returnans; }};Copy the code