leetcode 42 接雨水

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;
    }
};

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;
}