本文共 1369 字，大约阅读时间需要 4 分钟。

42.接雨水

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

暴力法

• 一个坐标可以接水的多少在于两边最高高度的比较小的那个减去当前坐标高度

class Solution {
   public:    int trap(vector
   
    & height) {
           if(height.size() < 2) return 0;        int res=0;            for(int i=1;i < height.size()-1;i++){
               int left = 0,right = 0;            for(int j=0;j < i+1;j++){
                   if(height[j] > left) left = height[j];            }            for(int j = i;j < height.size();j++){
                   if(height[j] > right) right = height[j];            }            res += min(left,right)-height[i];        }        return res;    }};
   

通过时间：

双指针

• 用双指针优化上个暴力法,把时间复杂度降到O(n)。

class Solution {
   public:    int trap(vector
   
    & height) {
           if(height.size() < 2) return 0;        int res=0;        int left=0,right=height.size()-1;        int maxleft=0,maxright=0;           while (left <= right) {
               if (maxleft <= maxright) {
                   if(height[left] > maxleft) maxleft = height[left];                res += maxleft - height[left];                left++;            } else {
                   if(height[right] > maxright) maxright = height[right];                res += maxright - height[right];                right--;            }        }         return res;    }};
   

通过时间：

转载地址：http://wsemb.baihongyu.com/