363.Trapping Rain Water-接雨水（中等题）

本文主要是介绍363.Trapping Rain Water-接雨水（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

接雨水

1. 题目

   给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。
   

2. 样例

   如上图所示，海拔分别为 [0,1,0,2,1,0,1,3,2,1,2,1], 返回 6.

3. 挑战

   O(n) 时间, O(1) 空间
   O(n) 时间, O(n) 空间也可以接受

4. 题解

   能接雨水的多少直接取决于左右端点的高度较小的那一个，使用双指针分别指向首末元素，每次选择高度小的指针向另一个指针移动，并和原来位置的高度进行比较，如果大于原指针位置元素高度则记录新的高度，反之将高度差作为雨水值保留，直至两指针相遇。

public class Solution {/*** @param heights: an array of integers* @return: a integer*/public int trapRainWater(int[] heights) {int result = 0;int left = 0;int right = heights.length-1;if (left >= right){return result;}int leftHeight = heights[left];int rightHeight = heights[right];while (left < right){if (heights[left] < heights[right]){left++;if (leftHeight > heights[left]){result += (leftHeight - heights[left]);}else{leftHeight = heights[left];}}else{right--;if (rightHeight > heights[right]){result += (rightHeight - heights[right]);}else{rightHeight = heights[right];}}}return result;}
}

Last Update 2016.11.8

这篇关于363.Trapping Rain Water-接雨水（中等题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---