题解 | #接雨水问题#

方法一

从左向右遍历，一般的，对第i个柱子，向右找j柱，使得以i柱为左边界，以j柱为右边界形成“凹水槽”。分两种情况

1. j柱是第一个大于或等于i柱的柱子，这时顺便计算“凹水槽”盛水量, i = j

2. 找不到大于或等于i柱的柱子，这时的j柱为i柱右边最大的柱子，也可以顺便计算“凹水槽”盛水量（至于怎么计算，请读者自己琢磨），i = j

   算法缺点：对于第2种情况，要高效的处理是比较困难的，方法可能还是存在的，但是空间代价一定不小。

方法二

对方法一改进，从两边遍历。从左向右遍历时如果遇到第二种情况，就后停下来。从右向左遍历与从左向右遍历对称。

这种算法克服了第一种情况的困难或性能差。

程序按第方法二实现。

class Solution {
public:
    int searchBiggerFromLeft(const vector<int>& arr, int beg, int end, long long &water)
    {
        int base = arr[beg];
        int j;
        for (j = beg + 1; j <= end; j++)
        {
            if (arr[j] != base)
            {
                break;
            }
        }

        beg = j - 1;        
        base = arr[beg];
        
        int i;
        for (i = beg + 1; i <= end; i++)
        {
            if (arr[i] < base)
            {
                water += base - arr[i];
            }
            else
            {
                break;
            }
        }

        if (i <= end)
        {
            return i;
        }

        water = 0;
        return beg;
    }
    
    int searchBiggerFromRight(const vector<int>& arr, int beg, int end, long long &water)
    {
        int base = arr[end];
        int j;
        for (j = end - 1; j >= beg; j--)
        {
            if (arr[j] != base)
            {
                break;
            }
        }

        end = j + 1;        
        base = arr[end];
        
        int i;
        for (i = end - 1; i >= beg; i--)
        {
            if (arr[i] < arr[end])
            {
                water += arr[end] - arr[i];
            }
            else
            {
                break;
            }
        }

        if (i >= beg)
        {
            return i;
        }

        water = 0;
        return end;
    }

    long long maxWater(vector<int>& arr) {
        // write code here
        long long sum = 0;
        int i = 0;
        int j = arr.size() - 1;
        while (i < j)
        {
            long long water = 0;
            int biggerIndex = searchBiggerFromLeft(arr, i, j, water); //找不到时返回输入的i,water为0
            i = biggerIndex;
            sum += water;

            water = 0;
            biggerIndex = searchBiggerFromRight(arr, i, j, water);    //找不到时返回输入的j,water为0
            sum += water;
            j = biggerIndex;
        }

        return sum;
    }
};