leetCode 42.Trapping Rain Water(凹槽的雨水) 解题思路和方法 _leetcode

赋料扬雄敌，诗看子建亲。这篇文章主要讲述leetCode 42.Trapping Rain Water(凹槽的雨水) 解题思路和方法相关的知识，希望能为你提供帮助。
Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

文章图片

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

思路：此题咋一看简单，可是细细思考。越想越复杂，感觉无从下手，无奈想了一天没搞定，仅仅能求助网上资料。最终思路例如以下：（网友非常强大）

（參考网址：http://www.xuebuyuan.com/1586534.html）

最后黑体字的Thanks Marcos的意思是让我们放大我们的想象力。由于上图非常easy误导我们的。假设仅仅有上图的情况的话，我们能够非常好用贪心法解决，可是。用贪心法是会出错的，由于假设我们计算当前最低点，然后往两边扩展找到两边递增的最高点，那么这个最高点非常可能是局部最高点，答案就会出错。

有两个解题思路：
1 两边往中间搜索
2 由左往右搜索，跳跃式计算
如以下的分析图，会比較直观：

文章图片

蓝色代表水，能够看见非常多局部最高点都被水淹了。

这里计算面积不用一般几何书的方法，这里是两边往中间遍历，记录当前第二高点secHight，然后利用这个第二高点减去当前历经的柱子。剩下就装水容量了。
为什么是第二高点？由于两边比較。最高的点不用动，仅仅移动第二高点。
【leetCode 42.Trapping Rain Water(凹槽的雨水) 解题思路和方法】第一个思路，依照上图的思想就能写出很简洁的程序了，时间复杂度为O(n)：

本人照着上面的思路写的代码例如以下：

public class Solution { public int trap(int[] height) { Stack< Integer> st = new Stack< Integer> (); if(height.length == 0) return 0; int i = 0; int j = height.length - 1; int ans = 0; //返回的答案 int secHight = 0; //第二个高度（最高的那个不动） while(i < j){ if(height[i] < height[j]){ secHight = Math.max(secHight,height[i]); //由于长度为1，高度也就是面积值。假设height[i]==secHight,则新增面积为0 ans += secHight - height[i]; i++; }else{ secHight = Math.max(secHight,height[j]); //由于长度为1，高度也就是面积值。假设height[i]==secHight,则新增面积为0 ans += secHight - height[j]; j--; } } return ans; } }