本文共 1432 字,大约阅读时间需要 4 分钟。
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!
Java代码:public class Solution { public int trap(int[] A) { int answer = 0; if (A.length <= 2) { answer = 0; } else { int maxValue = 0; int maxValueIndex = 0; for (int i = 0; i < A.length; i++) { int elem = A[i]; if (elem > maxValue) { maxValue = elem; maxValueIndex = i; } } int totalDrops = 0; int leftMax = 0; for (int i = 0; i < maxValueIndex; i++) { int elem = A[i]; if (elem > leftMax) { leftMax = elem; } else { totalDrops += leftMax - A[i]; } } int rightMax = 0; for (int i = A.length - 1; i > maxValueIndex; i--) { int elem = A[i]; if (elem > rightMax) { rightMax = elem; } else { totalDrops += rightMax - A[i]; } } answer = totalDrops; } return answer; }}
转载地址:http://onuni.baihongyu.com/