给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
方法1：暴力求解（超时）
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
long res = 0;
for(int i = 1; i < arr.length; i++) {
long maxLeft = 0;
for(int j = i; j >= 0; j--) {
maxLeft = Math.max(maxLeft, arr[j]);
}
long maxRight = 0;
for(int j = i; j < arr.length; j++) {
maxRight = Math.max(maxRight, arr[j]);
}
res += Math.min(maxRight, maxLeft) - arr[i];
}
return res;
}
}
方法2：双指针
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
//双指针
public long maxWater (int[] arr) {
long res = 0;
int left = 0, right = arr.length - 1;
int leftMax = 0, rightMax = 0;
while(left < right) {
leftMax = Integer.max(leftMax, arr[left]);
rightMax = Integer.max(rightMax, arr[right]);
if(leftMax < rightMax) {
res += leftMax - arr[left];
left++;
} else {
res += rightMax - arr[right];
right--;
}
}
return res;
}
}
方法3：动态规划
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
//双指针
public long maxWater (int[] arr) {
long res = 0;
int n = arr.length;
int[] leftMax = new int[n];
leftMax[0] = arr[0];
for(int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], arr[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[ i + 1], arr[i]);
}
for(int i = 0; i < n; i++) {
res += Math.min(leftMax[i], rightMax[i]) - arr[i];
}
return res;
}
}
