leetcode 42 接雨水

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

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
题解：感觉找到高度最大的从左边和右边开始往中间累加，于是有了如下代码

class Solution {
public:
    int trap(vector<int>& height) {
        int k = 1;
        
        int size = height.size();
        if(size == 0) return 0;
        int max = height[0]; //高度最大的柱子
        int index = 0;
        for(int i = 0; i < height.size(); i++)
        {
            if( height[i] > max)
            {
                max =height[i];
                index = i;
            }
        }
        int i = 0;
        int second = height[i];
        int res =0;
        while(i < index){ //左到最高
            if(i ==0)
            res += (index -i-1)*second;
            else if( height[i]<=second) res-=height[i]; //减去柱子
            else{ res -=second; res +=(height[i]-second)*(index-i-1); second=height[i];} //减去不够高的柱子，加上新高度的柱子存储的雨水
            i++;
        }
        int j = size-1;
        second=height[j];
        while(index < j)
        {
            if(j == size-1)
            res+=(j-1-index)*second;
            else if(height[j] <= second) res-=height[j];
            else{ res -=second; res +=(height[j]-second)*(j-1-index); second=height[j];}
            j--;
        }
        return res;
    }
};

上面的代码过了，高高兴兴去看题解发现，牛人太多。题解方法太多，而我的代码太麻烦。

大神题解1：

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        // left[i]表示i左边的最大值，right[i]表示i右边的最大值
        vector<int> left(n), right(n);
        for (int i = 1; i < n; i++) {
            left[i] = max(left[i - 1], height[i - 1]); //
        }
        for (int i = n - 2; i >= 0; i--) {
            right[i] = max(right[i + 1], height[i + 1]);
        }
        int water = 0;
        for (int i = 0; i < n; i++) {
            int level = min(left[i], right[i]);
            water += max(0, level - height[i]); //当前位置能存的水量
        }
        return water;
    }
};

官方双指针题解：

int trap(vector<int>& height)
{
    int left = 0, right = height.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (height[left] < height[right]) { //右边高，木桶原理，找左边
            height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
            ++left;
        }
        else { //同样左边高，木桶原理，找右边
            height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
            --right;
        }
    }
    return ans;
}

这些方法给力