C语言重构【42】接雨水

ゝ一世哀愁。 2022-12-25 09:56 153阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案1：动态规划
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

![在这里插入图片描述][20200514114326916.png]

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
    
    示例:
    
    输入: [0,1,0,2,1,0,1,3,2,1,2,1]
    输出: 6

#### 方案1：动态规划 ####

*  分别从左取元素的左最大值、从右取元素的右最大值，之后取二者较小值减去当前元素的值即可得出当前元素的积水量，图示如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]

#### 方案： ####

*  双指针，现在看看反而比动规好理解

class Solution
    { 
    public:
        int trap(vector<int> &height)
        { 
            //双指针
            int len = height.size();
            if (len < 3)
                return 0;
            //左边最高、右边最高
            int left = 0, right = len - 1;
            int li = 0, ri = right; //左右指针
            int sum = 0;
            int jud = 0; //0=li++ 1=ri--
            //如果右边比较埃，则右边先开始
            if (height[left] > height[right])
                jud = 1;
            while (li < ri)
            { 
                //若当前列<min(l,r),加上差值
                //若当前列至少比其中一个大，则替换小的
                if (jud == 0)
                { 
                    if (height[++li] > height[left])
                    { 
                        left = li;
                        //如果是比右边高，则换个方向
                        if (height[li] > height[right])
                            jud = 1;
                    }
                    else
                    { 
                        sum += height[left] - height[li];
                    }
                }
                else
                { 
                    if (height[--ri] > height[right])
                    { 
                        right = ri;
                        //如果是比左边高，则换个方向
                        if (height[ri] > height[left])
                            jud = 0;
                    }
                    else
                    { 
                        sum += height[right] - height[ri];
                    }
                }
            }
            return sum;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode
[20200514114326916.png]: /images/20221120/8eebcea517b449f8a268527744b9d15a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70]: /images/20221120/f2146f6f8b9a458290eb08ab6af2dc52.png