题目给定 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.length1 n 2 * 1040 height[i] 105题解class Solution { public int trap(int[] height) { int n height.length; int[] preMax new int[n]; preMax[0] height[0]; for(int i 1;i n;i){ //preMax[i] 记录的是 [0, i] 这个区间内出现的最高柱子高度。 preMax[i] Math.max(preMax[i - 1] , height[i]); } int[] sufMax new int[n]; sufMax[n - 1] height[n - 1]; for(int i n - 2;i 0;i--){ //sufMax[i] 记录的是 [i, n-1] 这个区间内出现的最高柱子高度。 sufMax[i] Math.max(sufMax[i 1] , height[i]); } int ans 0; for(int i 0;i n;i){ ans Math.min(preMax[i] , sufMax[i]) - height[i]; } return ans; } }思路按列接水对于数组中的任意一个位置 i它上方能存多少水完全取决于它左侧最高的柱子和右侧最高的柱子中较矮的那一个。存水公式当前位置存水量 min(左侧最高, 右侧最高) - 当前柱子高度。