leetcode-04
7. 接雨水https://leetcode.cn/problems/trapping-rain-water/给定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 sum0; for(int i0;iheight.length;i){ int leftMax0; int rightMax0; for(int j0;ji;j){ leftMaxMath.max(leftMax,height[j]); } for(int ji1;jheight.length;j){ rightMaxMath.max(rightMax,height[j]); } if(Math.min(leftMax,rightMax)-height[i]0){ sumMath.min(leftMax,rightMax)-height[i]; } } return sum; } }该方法在遍历每个柱子的时候都要遍历它左右侧的柱子可能会超时。可以提前遍历每个柱子左侧或右侧的最高柱子class Solution { public int trap(int[] height) { int nheight.length; int sum0; int [] leftMaxnew int [n]; leftMax[0]height[0]; for(int i1;in;i){ leftMax[i]Math.max(leftMax[i-1],height[i]); } int [] rightMaxnew int [n]; rightMax[n-1]height[n-1]; for(int in-2;i0;i--){ rightMax[i]Math.max(rightMax[i1],height[i]); } for(int i0;in;i){ sumMath.min(leftMax[i],rightMax[i])0?Math.min(leftMax[i],rightMax[i])-height[i]:0; } return sum; } }
