42. 接雨水

题目描述

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

image

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路

每个柱子可接的水量 = min(左边柱子高度，右边柱子高度) 与当前柱子高度的差。当然最左、最右柱子不可以接水。
所以可以定义两个数组left和right，分别存储i左边柱子的最大高度、i右边柱子的最大高度。

int trap(vector<int>& height){
    int length = height.size();
    if(length < 1)
        return 0;

    vector<int> left(length, 0);
    vector<Int> right(length, 0);

    int max_left = height[0];
    for(int i=1; i<length-1; i++){
        if(max_left<height[i])
            max_left = height[i];
        left[i] = max_left;
    }

    int max_right = height[length-1];
    for(int j=length-2; j>=0; j--){
        if(max_right<height[j])
            max_right = height[j];
        right[j] = max_right;
    }

    int ret = 0;
    for(int i=1; i<length-1; i++){
        int min_height = min(left[i], right[i]);
        ret += max(0, min_height-height[i]);
    }
    return ret;
}

更优解：双指针法，不需要设定left数组和right数组，仅保留max_left和max_right。这是因为计算每个位置的水量时，仅需要知道一边最小的高度就好。

• 当当前左边界<右边界，收集left处的水，左边界++
• 当当前左边界>有边界，收集right处的水，右边界--

    int trap(vector<int>& height) {
        int length = height.size();
        if(length<1)
            return 0;

        // max_left, 当前左边最大高度；max_right，当前右边最大高度
        int max_left = height[0], max_right = height[length-1];
        // left，当前左边收集下标；right，当前右边收集下标
        int left = 1, right = length - 2;
        int ret = 0;
        for(int i=1; i<length-1; i++){
            if(max_left<max_right){
                max_left = max(height[left], max_left);
                ret += max(0, max_left - height[left]);
                left++;
            }else{
                max_right = max(height[right], max_right);
                ret += max(0, max_right - height[right]);
                right--;
            }
        }
        
        return ret;
    }