42. 接雨水

题目：https://leetcode-cn.com/problems/trapping-rain-water/

代码：

class Solution {

    public int trap(int[] height) {
        int sum = 0;
        int left = getFirstLeft(height);
        int right;

        while (left < height.length-1) {
            right = getRight(height, left);
            //统计杯子中的水量
            sum = sum + (right - left-1) * Math.min(height[left], height[right]);
            //去掉杯底非水的部分
            for (int i = left + 1; i < right; i++) {
                sum = sum - height[i];
            }
            //找下一个杯子，此时新杯子的左杯壁为当前杯子的右杯壁
            left = right;
        }
        return sum;
    }

    /**
     * 获取第一个左杯壁的位置
     * @param height
     * @return
     */
    private int getFirstLeft(int[] height){
        for (int i = 0; i < height.length; i++) {
            if (height[i] >0) {
                //只要有高度，就算
                return i;
            }
        }
        return height.length;
    }

    /**
     * 获取右杯壁的位置
     * @param height
     * @param left
     * @return
     */
    private int getRight(int[] height, int left) {
        //默认右杯壁位置为整个数组的最右边
        int right = height.length-1;
        for (int i = left+1; i < height.length; i++) {
            //从左杯壁+1位置开始找
            if (height[i] >= height[left]) {
                //第一个高度大于等于左杯壁的就是右杯壁
                return i;
            } else if (height[i] > height[right]) {
                //如果上述条件找不到，即当前左杯壁已经是最高，则寻找右边元素中最高的值做右杯壁
                right = i;
            }
        }
        return right;
    }

}

因为数组是int类型，所以高度都是整数。一开始我的方案是将1个高度想象成1块砖头，设定一个水平线h，h=0，然后遍历数组，只要数组中的值小于h就代表本层这个位置是有水的，则水量+1，遍历结束之后水平线h自增1继续重复遍历直到水平线大于数组中最高的元素。简单来说思想就是一层一层的去计算水量，在数据量比较小的情况下，结果还是准确的，数据量一大耗时就太长了，而且我是真的没有想到最后一个测试用例的输入数据有一万多个数。直接导致超时没有ac，没办法，换方案呗。

新方案的思路如图：遍历数组，将数组划分成一个个装水的杯子，如图中红线所示。

对于杯子来说（二维空间条件下）一个杯子可以分成：左杯壁，右杯壁，杯底。而杯子中的水量=最矮杯壁*杯底宽度-杯底厚度。

仔细观察图，题目欲求的水量我们可以根据上述条件，转化成一个个杯子，通过计算每个杯子的水量之和即可得出答案。根据杯子水量的计算公式，我们需要知道每个杯子的左杯壁，右杯壁，杯底的宽度和厚度这四个变量。

左杯壁：从0位置开始，第一个有高度的值就可以作为左杯壁，而下一个杯子的左杯壁就是当前杯子的右杯壁。
右杯壁：从左杯壁的位置开始往右找，第一个大于左杯壁的值就是右杯壁，如果剩下的数据都没有比左杯壁还高，那么剩下的数据中最大的一个就是右杯壁。
杯底宽度：右杯壁-左杯壁-1
杯底厚度：遍历左杯壁到右杯壁的值，依次减去他们即可。

综上只需要将其转化成代码即可，具体的参考代码。值得骄傲的是，本方案还不错，打败了99.99%的用户。