题目描述

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。

示例:

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

分析

题目容易被所给的图带偏，其实给出简单的xy坐标图，就很容易想到解法。

关键是理解能存水的是单向递增（递减）的节点，存水的数量是任意两个递增（递减）节点间的数值小的节点所决定，公式为：（小节点值-区间内节点值）。

思路是从左往右，找递增节点，算出可存水数量，再从右往左找递增，但这时已经知道最大值节点（从左往右时得到），所以不用遍历整个数组，到最大值就可以结束。

代码

class Solution {

    public int trap(int[] height) {

        if(height.length == 0)

            return 0;

        int water = 0;

        int maxIndex = 0;

        int max = height[maxIndex];

        for (int i = 1; i < height.length; i++) {

            int cur = height[i];

            if (cur >= max) {

                if (maxIndex > -1) {

                    for (int j = maxIndex + 1; j < i; j++) {

                        water += max - height[j];

                    }

                }

                maxIndex = i;

                max = cur;

            }

        }

        int end = maxIndex;

        maxIndex = height.length - 1;

        max = height[maxIndex];

        for (int i = height.length - 2; i >= end; i--) {

            int cur = height[i];

            if (cur >= max) {

                if (maxIndex > -1) {

                    for (int j = maxIndex - 1; j > i; j--) {

                        water += max - height[j];

                    }

                }

                maxIndex = i;

                max = cur;

            }

        }

        return water;

    }

}