企业官网建设流程全解析

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.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

思路：每个柱子上的存水量等于该柱子左侧柱子高度的最大值与右侧柱子高度的最大值中较小的一个减去该柱子的高度

class Solution { public int trap(int[] height) { int sum=0; for(int i=0;i<height.length;i++){ int leftMax=0; int rightMax=0; for(int j=0;j<i;j++){ leftMax=Math.max(leftMax,height[j]); } for(int j=i+1;j<height.length;j++){ rightMax=Math.max(rightMax,height[j]); } if(Math.min(leftMax,rightMax)-height[i]>0){ sum+=Math.min(leftMax,rightMax)-height[i]; } } return sum; } }

该方法在遍历每个柱子的时候都要遍历它左右侧的柱子，可能会超时。

可以提前遍历每个柱子左侧或右侧的最高柱子

class Solution { public int trap(int[] height) { int n=height.length; int sum=0; int [] leftMax=new int [n]; leftMax[0]=height[0]; for(int i=1;i<n;i++){ leftMax[i]=Math.max(leftMax[i-1],height[i]); } int [] rightMax=new int [n]; rightMax[n-1]=height[n-1]; for(int i=n-2;i>=0;i--){ rightMax[i]=Math.max(rightMax[i+1],height[i]); } for(int i=0;i<n;i++){ sum+=Math.min(leftMax[i],rightMax[i])>0?Math.min(leftMax[i],rightMax[i])-height[i]:0; } return sum; } }