给定n个柱面的高度,表示降雨某地n块区域的海拔高度。
计算降雨之后该地最大储水面积。如果低于地平线,也就是小于0,则一定积水
class Solution { public int trap(int[] height) { if(height == null || height.length == 0) return 0; int left = 0, right = height.length - 1; int lmax = height[left], rmax = height[right]; int result = 0; while(left <= right) { lmax = Math.max(lmax, height[left]); rmax = Math.max(rmax, height[right]); if(lmax < rmax){ result += lmax - height[left]; left ++; }else{ result += rmax - height[right]; right --; } } return result; } }
/** * [1,3,5,2,6,0,9,10,8,2,7] * * @param ary * @return */ public static int caclPonding(int[] ary) { int maxIndex = findMaxIndex(ary); // 左右分开计算 int sumLeft = caclLeftPonding(ary, 0, maxIndex); int sumRight = caclRightPonding(ary, maxIndex, ary.length - 1); return sumLeft + sumRight; } private static int caclLeftPonding(int[] ary, int startIndex, int endIndex) { if (startIndex == endIndex) {// 递归终止 return 0; } int leftMaxIndex = findLeftMaxIndex(ary, startIndex, endIndex); int ponding = caclPonding(ary, leftMaxIndex, endIndex); return ponding + caclLeftPonding(ary, startIndex, leftMaxIndex); } private static int caclRightPonding(int[] ary, int startIndex, int endIndex) { if (startIndex == endIndex) {// 递归终止 return 0; } int rightMaxIndex = findRightMaxIndex(ary, startIndex, endIndex); int ponding = caclPonding(ary, startIndex, rightMaxIndex); return ponding + caclRightPonding(ary, rightMaxIndex, endIndex); } private static int caclPonding(int[] ary, int startIndex, int endIndex) { if (endIndex - startIndex < 2) { return 0; } int width = endIndex - startIndex - 1;// 间隔数 int height = ary[startIndex] > ary[endIndex] ? ary[endIndex] : ary[startIndex];// 取小值 int sum = 0; // 内部实体面积 for (int i = (startIndex + 1); i < endIndex; i++) { sum += ary[i]; } return width * height - sum; } public static int findMaxIndex(int[] ary) { int maxIndex = 0; int max = ary[maxIndex]; int length = ary.length; for (int i = 1; i < length; i++) { if (ary[i] > max) { max = ary[i]; maxIndex = i; } } return maxIndex; } public static int findLeftMaxIndex(int[] ary, int startIndex, int endIndex) { int maxIndex = startIndex; int max = ary[maxIndex]; for (int i = startIndex; i < endIndex; i++) { if (ary[i] >= max) {// 相等取最新的下标 max = ary[i]; maxIndex = i; } } return maxIndex; } public static int findRightMaxIndex(int[] ary, int startIndex, int endIndex) { int maxIndex = endIndex; int max = ary[maxIndex]; for (int i = endIndex; i > startIndex; i--) { if (ary[i] >= max) { max = ary[i]; maxIndex = i; } } return maxIndex; }