黑色的看成墙，蓝色的看成水，宽度一样，给定一个数组，每个数代表从左到右墙的高度，求出能装多少单位的水。也就是图中蓝色正方形的个数。

解法一 按行求

这是我最开始想到的一个解法，提交后直接 AC 了，自己都震惊了。就是先求高度为 1 的水，再求高度为 2 的水，再求高度为 3 的水。

整个思路就是，求第 i 层的水，遍历每个位置，如果当前的高度小于 i，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加 1。

如果求高度为 i 的水，首先用一个变量 temp 保存当前累积的水，初始化为 0 。从左到右遍历墙的高度，遇到高度大于等于 i 的时候，开始更新 temp。更新原则是遇到高度小于 i 的就把 temp 加 1，遇到高度大于等于 i 的，就把 temp 加到最终的答案 ans 里，并且 temp 置零，然后继续循环。

我们就以题目的例子讲一下。

先求第 1 行的水。

也就是红色区域中的水，数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。

原则是高度小于 1，temp ++，高度大于等于 1，ans = ans + temp，temp = 0。

temp 初始化为 0 ，ans = 0

height [ 0 ] 等于 0 < 1，不更新。

height [ 1 ] 等于 1 >= 1，开始更新 temp。

height [ 2 ] 等于 0 < 1， temp = temp + 1 = 1。

height [ 3 ] 等于 2 >= 1， ans = ans + temp = 1，temp = 0。

height [ 4 ] 等于 1 >= 1，ans = ans + temp = 1，temp = 0。

height [ 5 ] 等于 0 < 1， temp = temp + 1 = 1。

height [ 6 ] 等于 1 >= 1，ans = ans + temp = 2，temp = 0。

剩下的 height [ 7 ] 到最后，高度都大于等于 1，更新 ans = ans + temp = 2，temp = 0。而其实 temp 一直都是 0 ，所以 ans 没有变化。

再求第 2 行的水。

也就是红色区域中的水，

数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。

原则是高度小于 2，temp ++，高度大于等于 2，ans = ans + temp，temp = 0。

temp 初始化为 0 ，ans 此时等于 2。

height [ 0 ] 等于 0 < 2，不更新。

height [ 1 ] 等于 1 < 2，不更新。

height [ 2 ] 等于 0 < 2， 不更新。

height [ 3 ] 等于 2 >= 2， 开始更新

height [ 4 ] 等于 1 < 2，temp = temp + 1 = 1。

height [ 5 ] 等于 0 < 2， temp = temp + 1 = 2。

height [ 6 ] 等于 1 < 2， temp = temp + 1 = 3。

height [ 7 ] 等于 3 >= 2， ans = ans + temp = 5，temp = 0。

height [ 8 ] 等于 2 >= 2， ans = ans + temp = 3，temp = 0。

height [ 9 ] 等于 1 < 2， temp = temp + 1 = 1。

height [ 10 ] 等于 2 >= 2， ans = ans + temp = 6，temp = 0。

height [ 11 ] 等于 1 < 2， temp = temp + 1 = 1。

然后结束循环，此时的 ans 就是 6。

再看第 3 层。

按照之前的算法，之前的都是小于 3 的，不更新 temp，然后到 height [ 7 ] 等于 3，开始更新 temp，但是后边没有 height 大于等于 3 了，所以 ans 没有更新。

所以最终的 ans 就是 6。

看下代码吧。

publicinttrap(int[] height) {
intsum=0;
intmax=getMax(height);//找到最大的高度，以便遍历。for (inti=1; i<=max; i++) {
booleanisStart=false; //标记是否开始更新 tempinttemp_sum=0;
for (intj=0; j<height.length; j++) {
if (isStart&&height[j] <i) {
temp_sum++;
            }
if (height[j] >=i) {
sum=sum+temp_sum;
temp_sum=0;
isStart=true;
            }
        }
    }
returnsum;
}
privateintgetMax(int[] height) {
intmax=0;
for (inti=0; i<height.length; i++) {
if (height[i] >max) {
max=height[i];
        }
    }
returnmax;
}

时间复杂度：如果最大的数是 m，个数是 n，那么就是 O（m * n）。

空间复杂度： O （1）。

经过他人提醒，这个解法现在 AC 不了了，会报超时，但还是放在这里吧。 下边讲一下， leetcode solution 提供的 4 个算法。

解法二 按列求

求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。

装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。

所以，根据较矮的那个墙和当前列的墙的高度可以分为三种情况。

• 较矮的墙的高度大于当前列的墙的高度把正在求的列左边最高的墙和右边最高的墙确定后，然后为了方便理解，我们把无关的墙去掉。这样就很清楚了，现在想象一下，往两边最高的墙之间注水。正在求的列会有多少水？
  很明显，较矮的一边，也就是左边的墙的高度，减去当前列的高度就可以了，也就是 2 - 1 = 1，可以存一个单位的水。
  
• 较矮的墙的高度小于当前列的墙的高度同样的，我们把其他无关的列去掉。
• 想象下，往两边最高的墙之间注水。正在求的列会有多少水？
  正在求的列不会有水，因为它大于了两边较矮的墙。
  
• 较矮的墙的高度等于当前列的墙的高度。
  和上一种情况是一样的，不会有水。
• 明白了这三种情况，程序就很好写了，遍历每一列，然后分别求出这一列两边最高的墙。找出较矮的一端，和当前列的高度比较，结果就是上边的三种情况。

publicinttrap(int[] height) {
intsum=0;
//最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2for (inti=1; i<height.length-1; i++) {
intmax_left=0;
//找出左边最高for (intj=i-1; j>=0; j--) {
if (height[j] >max_left) {
max_left=height[j];
            }
        }
intmax_right=0;
//找出右边最高for (intj=i+1; j<height.length; j++) {
if (height[j] >max_right) {
max_right=height[j];
            }
        }
//找出两端较小的intmin=Math.min(max_left, max_right);
//只有较小的一段大于当前列的高度才会有水，其他情况不会有水if (min>height[i]) {
sum=sum+ (min-height[i]);
        }
    }
returnsum;
}

时间复杂度：O（n²），遍历每一列需要 n，找出左边最高和右边最高的墙加起来刚好又是一个 n，所以是 n²。

空间复杂度：O（1）。

总

解法二，空间换时间，这一系列下来，让人心旷神怡。