一、题目描述
给定 n 个非负整数表示每个宽度为 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
二、思路讲解
总蓄水量可以拆分为每个坐标的蓄水量，而每个坐标的蓄水量其实取决于自身高度和它左右两边的最高的那个柱子，因为木桶效应，应该由左边最高的柱子和右边最高的柱子中最矮的那根柱子决定，即一个坐标内的蓄水量 = min{左边柱子最高高度，右边柱子最高高度} - 自身高度，在自身高度小于左边和右边的情况下。
在力扣官方题解中看到很有意思的一张图：
三、代码实现
1、暴力
class Solution { public int trap(int[] height) { int sum = 0; for(int i=1; i<=height.length-2; i++){ int hei_min = find(height, i); if(hei_min > height[i]){ sum += (hei_min-height[i]); } } return sum; } //找到左边最高柱子 和 右边最高柱子 中较矮的那一个 int find(int []height, int i){ int left = height[0]; int right = height[i+1]; for(int k=0; k<i; k++){ left = Math.max(left, height[k]); } for(int k=i+1; k<height.length; k++){ right = Math.max(right, height[k]); } return Math.min(left, right); } }
时间复杂度： O(N^2)
空间复杂度： O(1)
2、动态规划
暴力解法的时间复杂度显然太高了，我们可以使用动态规划降低一下时间复杂度。
使用动态规划，通过一遍遍历，将每个位置的左右最高保存下来。这样只用一重循环即可。
class Solution { public int trap(int[] height) { int len = height.length; if(len == 0){ return 0; } int []left_max = new int[len]; int []right_max = new int[len]; left_max[0] = height[0]; right_max[len-1] = height[len-1]; left_max[0] = height[0]; right_max[0] = height[0]; //找出每个位置的左边最高的高度 for(int i=1; i<len; i++){ left_max[i] = Math.max(left_max[i-1], height[i]); } //找出每个位置的右边最高的高度 for(int i=len-2; i>=0; i--){ right_max[i] = Math.max(right_max[i+1], height[i]); } int res = 0; for(int i=0; i<len; i++){ int hei = Math.min(left_max[i], right_max[i]); if(hei > height[i]){ res += (hei-height[i]); } } return res; } }
时间复杂度： O(N)
空间复杂度： O(N)
3、双指针
那能不能把空间优化一下呢？
其实仔细观察不难发现，当某个位置的一侧有更高的柱子时，这个位置的蓄水量仅由另一侧决定
public int trap(int[] height) { int left = 0, right = height.length - 1; int ans = 0; int left_max = 0, right_max = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= left_max) { left_max = height[left]; } else { ans += (left_max - height[left]); } ++left; } else { if (height[right] >= right_max) { right_max = height[right]; } else { ans += (right_max - height[right]); } --right; } } return ans; }
时间复杂度： O(N)
空间复杂度： O(1)
