錯誤解法：若height[left]>height[right]則代表有坑

class Solution {public int trap(int[] height) {int left = 0;int area = 0;while(left<height.length-1){// 找坑int right = left+1;while(right<height.length-1 && height[left]>height[right]){right++;}// 計算第i個坑的面積int length_i = right-left-1;// 取小的那邊作為高int height_i = height[left]<height[right]?height[left]:height[right];int area_i = length_i * height_i;  // 忽略里面存在石頭// 刪除里面的石頭for(int i=left+1;i<right;i++){area_i = area_i - height[i];}// 加入第i個坑的面積area = area + area_i;left = right;}return area;}
}

注意：

• 在for循環中，條件為i<num.length；但在while循環中，條件為i<num.length-1

錯誤原因：右邊仍滿足條件，但沒坑

正確解法：預先計算每根柱子的左側最高柱子(包含該柱子本身)和右側最高柱子(包含該柱子本身)，然后再一次遍歷計算每個柱子能接的雨水量。

class Solution {public int trap(int[] height) {// 計算每個柱子的左邊最大值int[] leftMax = new int[height.length]; leftMax[0] = height[0];for(int i=1; i<height.length; i++){leftMax[i] = Math.max(leftMax[i-1], height[i]);}// 計算每個柱子的右邊最大值int[] rightMax = new int[height.length]; rightMax[height.length-1] = height[height.length-1];for(int i=height.length-2; i>=0; i--){rightMax[i] = Math.max(rightMax[i+1], height[i]);} // 計算每個柱子的接水量int area = 0;for(int i=0; i<height.length; i++){area = area + (Math.min(leftMax[i], rightMax[i]) - height[i]);}return area;}
}