链接：https://leetcode.cn/problems/trapping-rain-water/solution/san-chong-by-xun-ge-v-3op9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路

1. 动态规划

使用动态规划思路，就是对暴力求解进行优化过程，定义两个dp数组，一个保存左边最大值，一个保存右边最大值，遍历数组枚举每一个元素与对应左边和右边最大值的大小情况

• 当前元素与左边和右边最大值都小，说明此处可以存水
• 当前元素与左边或右边最大值小，说明此处可以不能存水，因为有一边会漏

具体实现看下面代码，有注释

1. 栈

使用单调递减栈
理解题目，参考图解，注意题目的性质，当后面的柱子高度比前面的低时，是无法接雨水的
当找到一根比前面高的柱子，就可以计算接到的雨水
所以使用单调递减栈对更低的柱子入栈
更低的柱子以为这后面如果能找到高柱子，这里就能接到雨水，所以入栈把它保存起来
平地相当于高度 0 的柱子，没有什么特别影响
当出现高于栈顶的柱子时
说明可以对前面的柱子结算了
计算已经到手的雨水，然后出栈前面更低的柱子

计算雨水的时候需要注意的是
雨水区域的右边 r 指的自然是当前索引 i
底部是栈顶 st.top() ，因为遇到了更高的右边，所以它即将出栈，使用 cur 来记录它，并让它出栈
左边 l 就是新的栈顶 st.top()
雨水的区域全部确定了，水坑的高度就是左右两边更低的一边减去底部，宽度是在左右中间
使用乘法即可计算面积

具体实现看下面代码，有注释

1. 双指针

双指针思路与动态规划差不多

具体实现看下面代码，有注释

代码

动态规划

//动态规划
#define MAX(a , b) ((a) > (b) ? (a) : (b))
 
int trap(int* height, int heightSize){
    int dpLeft[heightSize];//定义左边最大值
    dpLeft[0] = height[0];
    int dpRight[heightSize];//定义右边最大值
    dpRight[heightSize-1] = height[heightSize-1];
    int conut = 0;
    for(int i = 1; i < heightSize; i++)//单指针，线性扫描
    {
        dpLeft[i] = MAX(dpLeft[i-1] , height[i]);//保存左边最大值
        dpRight[heightSize - i - 1] = MAX(dpRight[heightSize - i] , height[heightSize - 1 - i]);//保存右边最大值
    }
    for(int i = 0; i < heightSize; i++)//遍历dp数组
    {
        if(height[i] >= dpLeft[i] || height[i] >= dpRight[i])
        {
            continue;
        }
        int min = dpLeft[i] < dpRight[i] ? dpLeft[i] : dpRight[i];//保存最小边
        conut += min - height[i]; //保存雨水
    }
    return conut;
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/trapping-rain-water/solution/san-chong-by-xun-ge-v-3op9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

栈

//栈
int trap(int* height, int heightSize) {
    int n = heightSize;
    if (n == 0) {
        return 0;
    }
    int ans = 0;
    int stk[n], top = 0;//初始化变量
    for (int i = 0; i < n; ++i) {//遍历数组
        while (top && height[i] > height[stk[top - 1]]) {//栈不为空，并当前元素将破坏栈的递减性，将栈元素弹出，直达维护栈递减
            int stk_top = stk[--top];//弹出栈顶元素
            if (!top) {//弹出后栈为空，说明两个元素挨在一起，肯定存不了水，
                break;
            }
            int left = stk[top - 1];//取左边界
            int currWidth = i - left - 1;
            int currHeight = fmin(height[left], height[i]) - height[stk_top];//计算高和底
            ans += currWidth * currHeight;//保存水面积，如果此时栈还是未递减，继续弹出元素
        }
        stk[top++] = i;
    }
    return ans;
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/trapping-rain-water/solution/san-chong-by-xun-ge-v-3op9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

双指针

//双指针
int trap(int* height, int heightSize){
    int leftMax = -1;
    int rightMax = -1;
    int left = 0;
    int right = heightSize - 1;
    int conut = 0;//定义初始化变量
    while(left < right)//左右遍历数组
    {
        if(height[left] < height[right])//右边高
        {
            if(height[left] >= leftMax)//当前更高，肯定存不水
            {
                leftMax = height[left];
            }
            else//比左边最大值小，并且左边比右边小，所以此处肯定是底处，下同，只是反过来
            {
                conut += leftMax - height[left];
            }
            left++;
        }
        else//左边高
        {
            if(height[right] >= rightMax)
            {
                rightMax = height[right];
            }
            else
            {
                conut += rightMax - height[right];
            }
            right--;
        }
    } 
    return conut;
}
 
作者：xun-ge-v
链接：https://leetcode.cn/problems/trapping-rain-water/solution/san-chong-by-xun-ge-v-3op9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。