LeetCode - Trapping Rain Water 等雨水的凹槽容量

作者：disappearedgod
文章出处：http://blog.csdn.net/disappearedgod/article/details/37510665

时间：2014-7-7

题目

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!

解法

解法一：

靖心的博客中已经详细分析了这道题的意思。

我的想法是：

• 数学解法是先算一个规则图形（凸包图形），然后再在图形上减去这个已有数组的值。

public class Solution {public int trap(int[] A) {int Height = 0;int left = 0;int right = A.length - 1;int area = 0;while(left < right){if(A[left] < A[right]){Height = Math.max(Height,A[left]);area +=Height - A[left];left++;}else{Height = Math.max(Height,A[right]);area += Height - A[right];right--;}}return area;}
}

参考

【1】LeetCode Trapping Rain Water等雨水的凹槽容量

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！