技巧

42_接雨水

class Solution {public int trap(int[] height) {int LMax = 0, RMax = 0;int len = height.length;int[] L2R = new int[len];int[] R2L = new int[len];//計數每一個格的左右邊最高柱for (int i = 0; i < len; i++) {LMax = Math.max(LMax, height[i]);L2R[i] = LMax;RMax = Math.max(RMax, height[len - 1 - i]);R2L[len - 1 - i] = RMax;}int countWater = 0;for (int i = 0; i < len; i++) {//當前格能接多少雨水由左邊最高柱子和右邊最高柱子中矮的決定,//然后再看當前格的柱子占了多少空間,還剩多少空間供雨水存//如果是負數就是存不了int currentCountWater = Math.min(L2R[i], R2L[i]) - height[i];if (currentCountWater > 0) {countWater += currentCountWater;}}return countWater;}
}