题目

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water

我的解法

我自己的思路是将整体按水池划分，从左到右找到一个个尽量大的水池，与括号匹配有点区别。设两个指针：left代表左墙，right代表右墙；因为水池以短边为主储水，left存在两种情况：高边或短边。 时间复杂度为 ) O ( n 2 ) )O(n^2) )O(n2)，空间复杂度为$O(1)$。

自己想的粗略版本，不够优，初学者自己花几小时想出来的，想记录下（轻喷）

class Solution {public int trap(int[] height) {int left = 0, right = 0, sum = 0, p = 0, temp = 0; //temp临时right值，p为临时right坐标if (height.length < 3) return 0;while (height[left] == 0 && left < height.length) { //起始不能为0left ++;}right = left;while (left < height.length - 1) {for (int i = left + 1; i < height.length; i++) {//left作为短边if (height[i] > height[left]) {right = i;if (right > left + 1) {for (int j = left + 1; j < right; j++) {sum += (height[left] - height[j]);}}left = right;temp = 0;p = 0;break;}else {//left作为高边或齐（等高）边if (i != height.length - 1) {if (temp < height[i]) {temp = height[i];p = i;}continue;}else {if (temp < height[i]) {temp = height[i];p = i;}if (p != 0) {right = p;}if (right > left + 1) {for (int j = left + 1; j < right; j++) {sum += (height[right] - height[j]);}left = right;}else {left ++;}temp = 0;p = 0;break;}}}}return sum;}
}

大神的解法

作者：windliang
链接：https://leetcode.cn/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/

解法一：按行求

整个思路就是，求第 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。代码如下。

public int trap(int[] height) {int sum = 0;int max = getMax(height);//找到最大的高度，以便遍历。for (int i = 1; i <= max; i++) {boolean isStart = false; //标记是否开始更新 tempint temp_sum = 0;for (int j = 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;}}}return sum;
}
private int getMax(int[] height) {int max = 0;for (int i = 0; i < height.length; i++) {if (height[i] > max) {max = height[i];}}return max;
}

时间复杂度：如果最大的数是$m$，个数是$n$，那么就是 $O(m\ast n)$。

空间复杂度：$O(1)$。

解法二：按列求

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

装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。所以，根据较矮的那个墙和当前列的墙的高度可以分为三种情况。

• 较矮的墙的高度大于当前列的墙的高度
  
  把正在求的列左边最高的墙和右边最高的墙确定后，然后为了方便理解，我们把无关的墙去掉。
  
  这样就很清楚了，现在想象一下，往两边最高的墙之间注水。正在求的列会有多少水？

很明显，较矮的一边，也就是左边的墙的高度，减去当前列的高度就可以了，也就是 2 - 1 = 1，可以存一个单位的水。

• 较矮的墙的高度小于当前列的墙的高度
  
  想象下，往两边最高的墙之间注水。正在求的列会有多少水？

正在求的列不会有水，因为它大于了两边较矮的墙。

• 较矮的墙的高度等于当前列的墙的高度。
• 和上一种情况是一样的，不会有水。
  
  明白了这三种情况，程序就很好写了，遍历每一列，然后分别求出这一列两边最高的墙。找出较矮的一端，和当前列的高度比较，结果就是上边的三种情况。

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

时间复杂度： O ( n 2 ） O(n^2） O(n2），遍历每一列需要 $n$，找出左边最高和右边最高的墙加起来刚好又是一个 nnn，所以是 n 2 n^2 n2 。
空间复杂度：$O(1$。

解法三: 动态规划

我们注意到，解法二中。对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度，这里我们可以优化一下。

首先用两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和 leetcode 上边的讲的有些不同）

对于 max_left我们其实可以这样求。max_left [i] = Max(max_left [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。

对于 max_right我们可以这样求。max_right[i] = Max(max_right[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。

这样，我们再利用解法二的算法，就不用在 for 循环里每次重新遍历一次求max_left和 max_right 了。

public int trap(int[] height) {int sum = 0;int[] max_left = new int[height.length];int[] max_right = new int[height.length];for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;
}

解法四：栈

说到栈，我们肯定会想到括号匹配了。我们仔细观察蓝色的部分，可以和括号匹配类比下。每次匹配出一对括号（找到对应的一堵墙），就计算这两堵墙中的水。我们用栈保存每堵墙。

当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。

如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。计算完，就把当前的墙继续入栈，作为新的积水的墙。

总体的原则就是，当前高度小于等于栈顶高度，入栈，指针后移。

当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

而对于计算 current 指向墙和新的栈顶之间的水，根据图的关系，我们可以直接把这两个墙当做之前解法三的 max_left 和 max_right，然后之前弹出的栈顶当做每次遍历的 height [ i ]。水量就是 Min ( max _ left ，max _ right ) - height [ i ]，只不过这里需要乘上两个墙之间的距离。可以看下代码继续理解下。

public int trap6(int[] height) {int sum = 0;Stack<Integer> stack = new Stack<>();int current = 0;while (current < height.length) {//如果栈不空并且当前指向的高度大于栈顶高度就一直循环while (!stack.empty() && height[current] > height[stack.peek()]) {int h = height[stack.peek()]; //取出要出栈的元素stack.pop(); //出栈if (stack.empty()) { // 栈空就出去break; }int distance = current - stack.peek() - 1; //两堵墙之前的距离。int min = Math.min(height[stack.peek()], height[current]);sum = sum + distance * (min - h);}stack.push(current); //当前指向的墙入栈current++; //指针后移}return sum;
}

时间复杂度：虽然 while 循环里套了一个 while 循环，但是考虑到每个元素最多访问两次，入栈一次和出栈一次，所以时间复杂度是 $O(n)$。
空间复杂度：$O(n)$。栈的空间。

非常佩服大神的思路，思路不一样写出的代码简直是云泥之别，质量相差非常大。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！