题目

接雨水 给定 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

思路

1.暴力，遍历位置 i 时，嵌套循环，找到位置 i 左右两边的最高度，计算每个位置接雨水的量

class Solution { public int trap(int[] height) { // 暴力，计算每个位置i的接雨水量时， // 内嵌循环，计算位置i左边和右边的最大高度 if(height == null || height.length == 0) return 0; int res = 0; for(int i = 1; i < height.length - 1; i++) { int leftMax = 0, rightMax = 0; for(int j = i; j >= 0; j--) { leftMax = Math.max(leftMax, height[j]); } for(int k = i; k < height.length; k++) { rightMax = Math.max(rightMax, height[k]); } res += Math.min(leftMax, rightMax) - height[i]; } return res; } }

2.dp, 先遍历height, 记录每个位置左右两边的最大高度, 再遍历依次height, 计算每个位置i能接雨水量 即记住每个位置左边和右边的最大值，不用每次到位置i时都要去找

class Solution { public int trap(int[] height) { // dp, 先遍历一遍height， 记录每个位置左边和右边的最大值， // 不用每次到位置i , 都要内嵌一次循环寻找每个位置i 左边和右边的最大值 if(height == null || height.length == 0) return 0; int n = height.length; int[][] dp = new int[n][2]; dp[0][0] = height[0]; dp[n-1][1] = height[n-1]; int res = 0; for(int i = 1; i < height.length; i++) { dp[i][0] = Math.max(dp[i-1][0], height[i]); } for(int i = n - 2; i >= 0; i--) { dp[i][1] = Math.max(dp[i+1][1], height[i]); } for(int i = 1; i < n - 1; i++) { res += Math.min(dp[i][0], dp[i][1]) - height[i]; } return res; } }

出错：

dp[0][0] 不是0， dp[n-1][1]不是0 dp[0][0] = height[0]; dp[n-1][1] = height[n-1];左边从第二个位置开始遍历，右边从倒数第二个位置开始遍历 for(int i = 1; i < height.length; i++) for(int i = n - 2; i >= 0; i–)

3.双指针left++, right–，左右夹击遍历一次，根据leftMax一定是位置left左边的最大值，rightMax不一定是位置left右边的最大值；同理，rightMax一定是位置right右边的最大值，不一定是位置right左边的最大值； 当leftMax < rightMax, leftMax就一定是位置left左右两边的最大高度的较小者；因为位置left的右边高度最大值 >= rightMax；

class Solution { public int trap(int[] height) { // 双指针left, right，左右夹击遍历 // left: 当leftMax < rightMax , leftMax就是位置i的两边较小者 // right: 当ritghtMax > leftMax, rightMax就是位置i的两边较小者 if(height == null || height.length < 3) return 0; int n = height.length; int left = 1, right = n - 2; int leftMax = height[0], rightMax = height[n-1]; int res = 0; while(left <= right) { if(leftMax < rightMax) { res += Math.max(0, leftMax - height[left]); leftMax = Math.max(leftMax, height[left]); left++; }else { res += Math.max(0, rightMax - height[right]); rightMax = Math.max(rightMax, height[right]); right--; } } return res; } }

4.单调栈，

// for遍历全部柱子 // 如果栈为空，则柱子直接入栈 // 如果元素小于栈顶的元素，入栈。 // 如果元素大于栈顶的元素，说明此时栈顶可以接雨水，因为栈内元素是递减的 // 栈顶下面的元素大于栈顶，新来的元素也大于栈顶， // 弹出栈顶元素，计算接雨水的量

图：https://leetcode-cn.com/problems/trapping-rain-water/solution/dan-diao-zhan-jie-jue-jie-yu-shui-wen-ti-by-sweeti/

class Solution { public int trap(int[] height) { // 遍历柱子，当栈为空，或遍历到的柱子小于栈顶柱子高度时(这样栈顶才会可能接雨水))，柱子存入栈中 // 当遍历到的柱子高度大于栈顶柱子高度时，弹出栈顶柱子高度，去计算接雨水的量 if(height == null || height.length < 3) return 0; int n = height.length; Stack<Integer> stack = new Stack(); int res = 0; for(int i = 0; i < n; i++) { while(!stack.isEmpty() && height[i] > height[stack.peek()]) { int buttomIndex = stack.pop(); while(!stack.isEmpty() && height[buttomIndex] == height[stack.peek()]) { stack.pop(); } if(!stack.isEmpty()) { res += (Math.min(height[i], height[stack.peek()]) - height[buttomIndex]) * (i - stack.peek() - 1); } } stack.push(i); } return res; } }