42. Trapping Rain Water

只要理解了题意，其实不是很难。关键就是找到图形中“凹陷”的地方，有几点要注意：

• 如果高度一直上升/一直下降/一直不变，是不可能存水的
• 每一个可以存水的位置，关键是如何找到左边界和右边界
• 左边界只可能是高度开始下降的位置
• 右边界有两种情况：1.比左边界高的第一个bar；2.如果右边所有的bar高度都小于左边界，就以最高的bar为右边界。

其中的原理想想就明白了。计算过程就是不断寻找左边界和右边界的过程。

public class Solution {
    public int trap(int[] height) {
        // 边界条件
        if (height == null || height.length <= 2)
            return 0;

        int begin = -1, end = -1;
        // 找到高度开始下降的一个点作为begin，[1,2,3,4,...]这种，1/2/3都不可能作为左边界
        for (int i = 0; i < height.length; i++) {
            if (i + 1 < height.length && height[i] > height[i + 1]) {
                begin = i;
                break;
            }
        }
        // 从尾部开始，找到高度开始上升的那个点作为end，比如[...,4,3,2,1]中，3/2/1都不可能是右边界
        for (int i = height.length - 1; i >= 0; i--) {
            if (i - 1 >= 0 && height[i - 1] < height[i]) {
                end = i;
                break;
            }
        }
        // 可以排除一些bad case
        if (begin == -1 || end == -1 || begin >= end)
            return 0;

        int result = 0;
        // i不会等于end，因为左边界不可能是最后一个元素
        for (int i = begin; i < end;) {
            // 找到高度开始“下降”的那个点
            if (i + 1 <= end && height[i] <= height[i + 1]) {
                i++;
                continue;
            }
            // 以i为左边界，向右寻找右边界
            // 右边界有两种情况：如果右侧有height>=height[i]的元素，就以这个元素为右边界
            // 否则，就以右边height最大的元素为右边界
            int leftIndex = i, rightIndex = -1;   // 左边界和右边界

            // 保存两个边界中间所有元素height的和，最后计算存水量时要减去这个
            // 两个变量分别对应右边界的两种情况
            int sum1 = 0, sum2 = 0;
            int maxHeight = -1, maxHeightIndex = -1;
            for (int j = i + 1; j <= end; j++) {
                if (height[j] > maxHeight) {
                    maxHeight = height[j];
                    maxHeightIndex = j;
                    sum2 = sum1;
                }
                if (height[j] < height[i]) {
                    sum1 += height[j];
                }
                // 找到了比左边界高的第一个bar作为右边界
                else {
                    rightIndex = j;
                    break;
                }
            }

            if (rightIndex != -1) {
                result = result + (rightIndex - leftIndex - 1) * height[leftIndex] - sum1;
                i = rightIndex;
            } else {
                result = result + (maxHeightIndex - leftIndex - 1) * maxHeight - sum2;
                i = maxHeightIndex;
            }
        }

        return result;
    }
}