首页 > 代码库 > [LeetCode]42 Trapping Rain Water
[LeetCode]42 Trapping Rain Water
https://oj.leetcode.com/problems/trapping-rain-water/
http://fisherlei.blogspot.com/2013/01/leetcode-trapping-rain-water.html
public class Solution {
public int trap(int[] A) {
// 对于某坐标 有
// - leftmax 它左边最高
// - rightmax 它右边最高
// - val 它本身高度
// 那么它的容积为 max( min(leftmax, rightmax) - val, 0 )
// 那么从左向右遍历 创建 leftmax[]
// 类似 从右向左遍历 创建 rightmax[]
// 最后遍历一遍 计算容积 求和
// O(n)
// Input validations.
if (A == null || A.length == 0)
return 0; // Invalid input.
int len = A.length;
// Build leftmax[]
int[] leftmax = new int[len];
int seenleftmax = 0;
for (int i = 0 ; i < len ; i ++)
{
leftmax[i] = seenleftmax;
if (A[i] > seenleftmax)
seenleftmax = A[i];
}
// Build rightmax[]
int[] rightmax = new int[len];
int seenrightmax = 0;
for (int i = len - 1 ; i >= 0 ; i --)
{
rightmax[i] = seenrightmax;
if (A[i] > seenrightmax)
seenrightmax = A[i];
}
// Calculate result
int result = 0;
for (int i = 0 ; i < len ; i ++)
{
int v = Math.max(Math.min(leftmax[i], rightmax[i]) - A[i] , 0);
result += v;
}
return result;
}
}[LeetCode]42 Trapping Rain Water
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。