42.接雨水

本文主要是介绍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

·解题思路

————————暴力求解（最直接的想法）——————

利用指针遍历，left和right两个指针left从0到n-2，right 在left右边。当right移动遇见元素大于或者等于原始left元素的时候，说明形成凹陷，可以载雨水。

这个的问题在于，当最初始的left为最大元素，而right到达边界也不能大于或等于原始left元素，但是载该内部有小凹陷可以存在雨水，也就是需要对于边界条件进行处理。

解决办法，引入了有边界寻找的条件判断。当可以寻找到右边界，那么就是简单处理。如果寻找不到右边界，寻找从边界条件处left往后的最大元素（不包括left），将最大元素作为right边界计算凹形面积。再left = right 迭代。

为什么要用最大元素作为边界条件呢？这是以为从右边界往前，最大元素会阻挡凹陷。

·代码java

class Solution {public int trap(int[] height) {int n = height.length;int left = 0;int area = 0;while(left < n - 1){if(height[left] < height[left + 1]){left ++;continue;}int count = 0;int right = left + 1;boolean fond = false;while(right < n){if(height[right] >= height[left]){fond = true;break;}count += height[right];right ++;}if(fond){int H = Math.min(height[left], height[right]);int W = right - left - 1;area += H * W - count;left = right ;}else {int MaxIndex = left + 1;for(int i = left + 1; i < n; i++) {if (height[i] > height[MaxIndex]) {MaxIndex = i;}}right = MaxIndex;count = 0;for(int j = left + 1; j < right; j++){count += height[j];}int H = Math.min(height[left], height[right]);int W = right - left - 1;area += H * W - count;left = right ;}}return area;}
}

——————官方的动态规划——————

动态规划的原理在于：从左往右将小元素置为左边最大的元素；再从右往左，将小元素置为右边最大的元素。两次扫描的重叠区域再减去原有的数组就是可以盛水的区域。

·代码：

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

————————将两个数组该为双指针问题——————

从上述动态规划的算法中可以发现，最后的area叠加

area += Math.min(leftMax[i], rightMax[i]) - height[i];

那么可以利用双指针将min计算步骤改为

(height[left] < height[right])

所以最后代码：

    public int trap(int[] height) {int n = height.length;int area = 0;int left =0, right = n - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = Math.max(leftMax, height[left]);rightMax = Math.max(rightMax, height[right]);if (height[left] < height[right]) {area += leftMax - height[left];left++;} else {area += rightMax - height[right];right--;}}return area;}

这篇关于42.接雨水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---