制作网站谁家做的好/百度推广计划

难度：hard

1、题目介绍

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

2、思路分析

1、第一种方法：暴力法

首先能想到的是求出每个柱子的存水量，在累加起来就好了。

         （1）、没跟柱子的存水量是：以当前柱子为起始点，找到左右俩边的最大值，用左右俩边最大值中的较少值 - 当前柱子的高度

        （2）、从第二根柱子开始 ，高度为2，左边最大值为 4，右边最大值 5 ，存水量 =  min(5,4)- 2 = 2

        （3）、第三根柱子，高度为 0 ，左边最大值为 4，右边最大值 5 ，存水量 =  min(5,4)- 0 = 4

        （4）、第四根柱子，高度为3， 左边最大值为 4，右边最大值 5 ，存水量 =  min(5,4)- 3 = 1

        （5）、第五根柱子 2，高度为2， 左边最大值为 4，右边最大值 5 ，存水量 =  min(5,4)- 2= 2

        （6）、最终的存水量 2 + 4 + 1  + 2  = 9

 private static int trap(int[] height) {int length = height.length;//保存最大存水量int max_trap = 0;//对每个柱子进行遍历，从第二个柱子开始for (int i = 1; i < length; i++) {int max_left = 0, max_right = 0;//找到 i 以左的最大值for (int j = i; j >= 0; j--) {max_left = Math.max(max_left, height[j]);}//找到 i 以右的最大值for (int j = i; j < length; j++) {max_right = Math.max(max_right, height[j]);}//当前 第 i个柱子的存水量 = 左右俩边最大值中的较少值 - 当前柱子的高度max_trap = Math.min(max_left, max_right) - height[i] + max_trap;}return max_trap;}

        2、第二种方法：动态规划

        由于每次遍历都需要找到左右俩边的最大值，我们可以找到这个值并提前保存这个值

        int length = height.length;//保存左右俩边的最大值int[] max_left = new int[length];int[] max_right = new int[length];int max_trap = 0 ;//找到每根柱子以左的最大值并保存起来max_left[0] = height[0];for (int i = 1; i < length; i++) {max_left[i] = Math.max(max_left[i-1],height[i]);}//找到每根柱子以右的最大值并保存起来max_right[length-1] = height[length-1];for (int i = length-2; i >= 0; i--) {max_right[i] = Math.max(max_right[i+1],height[i]);}//计算每根柱子的存水容量for (int i = 0; i < length; i++) {max_trap = Math.min(max_left[i],max_right[i]) - height[i] + max_trap;}return max_trap ;

 最终max_left 和 max_right 数组如下：

        第三种方法：双指针法 

        使用俩个指针分别指向数组的俩测，比较俩个指针的大小，哪边小就移动哪边的指针。 

  //采用双指针法public static int newTrap2(int[] height) {int max_trap = 0;int max_left = 0, max_right = 0;//左右指针，分别指向数组俩测int left = 0, right = height.length - 1;while (left < right) {//哪边小就移动哪边的指针，原因就是要求左右俩边最大值中的最小值//与 第 11 题：计算最大盛水容量思路类似if (height[left] < height[right]) {//找到左边的最大值if (height[left] >= max_left) {max_left = height[left];} else {//计算存水量，执行到此处说明 left指向的值就是左右俩边最大值中的较小值max_trap = max_left - height[left] + max_trap;}left++;} else {//找到右边最大值if (height[right] >= max_right) {max_right = height[right];} else {//计算存水量，执行到此处说明 right指向的值就是左右俩边最大值中的较小值max_trap = max_right - height[right] + max_trap;}right--;}}return max_trap;}