Trap Water
出处
You are given an array of n non-negative integers. Each value means the height of a histogram. Suppose you are pouring water onto them, what is the maximum water it can hold between a left bar and a right bar (no seperation)?
Solution
当前节点的解,取决于左右两边的海拔高度,可以左一遍DP求出左侧海拔高度,再右一遍DP求出右侧海拔高度,同时积累结果:当前节点的储水量,等于左侧最高海拔与右侧最高海拔的较小值减去当前节点的海拔。
对于任何一个坐标,检查其左右的最大坐标,然后相减就是容积。所以,
- 从左往右扫描一遍,对于每一个坐标,求取左边最大值。
- 从右往左扫描一遍,对于每一个坐标,求最大右值。
- 再扫描一遍,求取容积并加和。
Complexity
两轮遍历,时间复杂度 O(n),空间复杂度 O(n)
Code
int maxWater(int[] arr){
int len = arr.length;
if (len == 0) return 0;
int leftMax = 0;
int rightMax = 0;
int water = 0;
int[] dp = new int[len];
// from left
for (int i = 0; i < len - 1; i++){
dp[i] = leftMax;
if (arr[i] > leftMax){
leftMax = arr[i];
}
}
// from right
for (int i = len-1; i >= 0; i++){
if (Math.min(dp[i], rightMax) > arr[i]){
water += Math.min(dp[i], rightMax) - arr[i];
}
if (arr[i] > rightMax){
rightMax = arr[i];
}
}
return water;
}