算法-栈和队列：接雨水

给出一排宽度为1、高度为n的柱子，求可以接到雨水的面积。

思路解析：

1. 方法一：采用双指针解法，按列计算，第一个柱子和最后一个柱子不接雨水，因为宽度为1所以每一列的面积=min[左边最高高度,右边最高高度]-Height，如果小于0则取0。
2. 方法二：采用动态规划解法，和方法一类似，也是按列计算，但是为了避免重复计算，使用数组maxLeft保存每个位置的左边最高高度（当前位置的左边最高高度是前一个位置的左边最高高度和本高度比较后的最大值），使用数组maxRight保存每个位置的右边最高高度（当前位置的右边最高高度是后一个位置的右边最高高度和本高度比较后的最大值）。
   每一列的面积=min[左边最高高度,右边最高高度]-Height，如果小于0则取0。
3. 方法三：采用单调栈解法，按行计算，栈头为小的值（其实栈存下标就行，所以栈头是小的值对应的下标），进栈元素会出现以下几种情况：

• 如果要进栈的元素小于栈头，那么进栈；
• 如果要进栈的元素等于栈头，那么弹出原栈头，新元素进栈（因为按行计算的，所以下标需要用到）；
• 如果要进栈的元素大于栈头，那么遇到了凹槽，需要计算面积=行（进栈元素下标-栈头下面元素的下标-1）✖️高（这两个下标中较小的那个对应的值-栈头对应的值）。

方法一：

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

//方法一：采用双指针解法，按列计算，第一个柱子和最后一个柱子不接雨水，因为宽度为1所以每一列的面积=min[lHeight,rHeight]-Height，如果小于0则取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;
}

方法二：

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

//方法二：采用动态规划解法，和方法一类似，也是按列计算，但是为了避免重复计算，使用数组maxLeft保存每个位置的左边最高高度（当前位置的左边最高高度是前一个位置的左边最高高度和本高度比较后的最大值），使用数组maxRight保存每个位置的右边最高高度（当前位置的右边最高高度是后一个位置的右边最高高度和本高度比较后的最大值）。
//每一列的面积=min[左边最高高度,右边最高高度]-Height，如果小于0则取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;
}

方法三：

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

//方法三：采用单调栈解法，按行计算，栈头为小的值（其实栈存下标就行，所以栈头是小的值对应的下标）
//- 如果要进栈的元素小于栈头，那么进栈；
//- 如果要进栈的元素等于栈头，那么弹出原栈头，新元素进栈（因为按行计算的，所以下标需要用到）；
//- 如果要进栈的元素大于栈头，那么遇到了凹槽，需要计算面积=行（进栈元素下标-栈头下面元素的下标-1）✖️高（这两个下标中较小的那个对应的值-栈头对应的值）。

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()]) { //注意是while，因为nums[i]可能还是大于栈里的其他值
                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; //注意是-1，因为求的是中间长度
                    sum += h*w;
//                    st.pop();//错误！！！不弹出，因为还要把这个元素当作mid
                }
            }
            st.push(i);//直到当前元素小于等于栈头元素
        }
    }
    return sum;
}

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