LeetCode热题100--42. 接雨水--困难

题目

给定 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

题解

classSolution{publicinttrap(int[]height){intsum=0;intmax_left=0;intmax_right=0;intleft=1;intright=height.length-2;for(inti=1;i<height.length-1;i++){//从左到右更if(height[left-1]<height[right+1]){max_left=Math.max(max_left,height[left-1]);intmin=max_left;if(min>height[left]){sum=sum+(min-height[left]);}left++;//从右到左更}else{max_right=Math.max(max_right,height[right+1]);intmin=max_right;if(min>height[right]){sum=sum+(min-height[right]);}right--;}}returnsum;}}

解析

出自：详细通俗的思路分析，多解法

classSolution{publicinttrap(int[]height){// 初始化总储水量intsum=0;// 记录当前 left 指针左侧的最大高度（不包括 left 本身）intmax_left=0;// 记录当前 right 指针右侧的最大高度（不包括 right 本身）intmax_right=0;// 左指针：从索引 1 开始（因为边界无法积水）intleft=1;// 右指针：从倒数第二个位置开始（height.length - 2）intright=height.length-2;// 右边界也无法积水// 遍历中间所有可能积水的位置（共 n-2 次）for(inti=1;i<height.length-1;i++){// 【关键判断】：比较 left 左边和 right 右边的高度// 如果左边的“已知最大值”更小，则优先处理 left 侧if(height[left-1]<height[right+1]){// 更新 left 左侧的最大高度（到目前为止）max_left=Math.max(max_left,height[left-1]);// 当前能接水的高度由“左侧最大”决定（因为右侧至少有更大的挡板）intmin=max_left;// 如果左侧最大高度 > 当前柱子高度，则可以积水if(min>height[left]){sum=sum+(min-height[left]);// 累加积水量}// 左指针右移，处理下一个位置left++;// 否则，优先处理 right 侧}else{// 更新 right 右侧的最大高度（到目前为止）max_right=Math.max(max_right,height[right+1]);// 当前能接水的高度由“右侧最大”决定（因为左侧至少有更大的挡板）intmin=max_right;// 如果右侧最大高度 > 当前柱子高度，则可以积水if(min>height[right]){sum=sum+(min-height[right]);// 累加积水量}// 右指针左移，处理下一个位置right--;}}// 返回总储水量returnsum;}}