Algorithm - stack and queue: connected to rain

Give a row of columns with width of 1 and height of n, and calculate the area that can receive rainwater.

Train of thought analysis:

1. Method 1: using the double pointer method, calculate by column. The first column and the last column do not receive rainwater. Because the width is 1, the area of each column = min [the highest Height on the left and the highest Height on the right] - Height. If it is less than 0, take 0.
2. Method 2: adopt the dynamic programming solution, which is similar to method 1. It is also calculated by column, but in order to avoid repeated calculation, use the array maxLeft to save the left highest height of each position (the left highest height of the current position is the maximum value after comparing the left highest height of the previous position with this height), Use the array maxRight to save the maximum height on the right of each position (the maximum height on the right of the current position is the maximum value after comparing the maximum height on the right of the next position with this height).
   The area of each column = min [the highest Height on the left, the highest Height on the right] - Height. If it is less than 0, take 0.
3. Method 3: using the monotone stack solution, calculate by line, and the stack head is a small value (in fact, the stack saves the subscript, so the stack head is the subscript corresponding to the small value). The following situations will occur in the elements entering the stack:

• If the element to be put on the stack is smaller than the head of the stack, put it on the stack;
• If the element to be put into the stack is equal to the stack head, the original stack head will pop up and the new element will be put into the stack (because it is calculated by line, the subscript needs to be used);
• If the element to be pushed into the stack is larger than the stack head, the groove is encountered, and the area = row needs to be calculated (the subscript of the element to be pushed into the stack - the subscript of the element below the stack head - 1) ✖️ High (the value corresponding to the smaller of the two subscripts - the value corresponding to the stack head).

Method 1:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//Method 1: using the double pointer method, calculate by column. The first column and the last column do not receive rainwater. Because the width is 1, the area of each column = min[lHeight,rHeight]-Height. If it is less than 0, take 0.

int trap(vector<int> nums){
    int sum = 0;
    for(int i = 1; i < nums.size()-1; i++){
        int lHeight = nums[i];
        int rHeight = nums[i];
        for(int r = i+1; r < nums.size(); r++){
            if(nums[r] > rHeight){
                rHeight = nums[r];
            }
        }
        for(int l = i-1; l >= 0; l--){
            if(nums[l] > lHeight){
                lHeight = nums[l];
            }
        }
        int h = min(lHeight,rHeight)-nums[i];
        if(h > 0){
            sum += h;
        }
    }
    return sum;
}

int main(){
    vector<int> nums = {1,0,2,1,3,1,0,1,2,0,1};
    cout<<trap(nums)<<endl;
    return 0;
}

Method 2:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//Method 2: adopt the dynamic programming solution, which is similar to method 1. It is also calculated by column, but in order to avoid repeated calculation, use the array maxLeft to save the left highest height of each position (the left highest height of the current position is the maximum value after comparing the left highest height of the previous position with this height), Use the array maxRight to save the maximum height on the right of each position (the maximum height on the right of the current position is the maximum value after comparing the maximum height on the right of the next position with this height).
//The area of each column = min [the highest Height on the left, the highest Height on the right] - Height. If it is less than 0, take 0.

int trap(vector<int> nums){
    if(nums.size() <= 2){
        return 0;
    }
    int sum = 0;
    vector<int> maxLeft(nums.size(),0);
    vector<int> maxRight(nums.size(),0);
    maxLeft[0] = nums[0];
    maxRight[nums.size()-1] = nums[nums.size()-1];
    for(int i = 1; i < nums.size(); i++){
        maxLeft[i] = max(maxLeft[i-1],nums[i]);
    }
    for(int i = nums.size()-2; i >= 0; i--){
        maxRight[i] = max(maxRight[i+1],nums[i]);
    }
    for(int i = 1; i < nums.size()-1; i++){
        int h = min(maxLeft[i],maxRight[i])-nums[i];
        if(h > 0){
            sum += h;
        }
    }
    return sum;
}

int main(){
    vector<int> nums = {1,0,2,1,3,1,0,1,2,0,1};
    cout<<trap(nums)<<endl;
    return 0;
}

Method 3:

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

//Method 3: use the monotone stack solution, calculate by line, and the stack head is a small value (in fact, the stack saves the subscript, so the stack head is the subscript corresponding to the small value)
//-If the element to be put on the stack is smaller than the head of the stack, put it on the stack;
//-If the element to be put into the stack is equal to the stack head, the original stack head will pop up and the new element will be put into the stack (because it is calculated by line, the subscript needs to be used);
//-If the element to be pushed into the stack is larger than the stack head, the groove is encountered, and the area = row needs to be calculated (the subscript of the element to be pushed into the stack - the subscript of the element below the stack head - 1) ✖️ High (the value corresponding to the smaller of the two subscripts - the value corresponding to the stack head).

int trap(vector<int> nums){
    if(nums.size()<=2){
        return 0;
    }
    int sum = 0;
    stack<int> st;
    st.push(0);
    for(int i = 1; i < nums.size(); i++){
        if(nums[i] < nums[st.top()]){
            st.push(i);
        }
        else if(nums[i] == nums[st.top()]){
            st.pop();
            st.push(i);
        }
        else {
            while (!st.empty() && nums[i]>nums[st.top()]) { //Note that it is while, because nums[i] may still be greater than other values in the stack
                int mid = st.top();
                st.pop();
                if(!st.empty()){
                    int h = min(nums[i],nums[st.top()]) - nums[mid];
                    int w = i - st.top() - 1; //Notice that it's - 1, because it's the middle length
                    sum += h*w;
//                    st.pop();// Error!!! Don't pop up, because you have to treat this element as a mid
                }
            }
            st.push(i);//Until the current element is less than or equal to the stack header element
        }
    }
    return sum;
}

int main(){
    vector<int> nums = {1,0,2,1,3,1,0,1,2,0,1};
    cout<<trap(nums)<<endl;
    return 0;
}