1.題目描述
給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。
示例1：
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。
示例 2：
輸入：height = [4,2,0,3,2,5]
輸出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
package com.iptv.prefecture.test;/*** @author: zhoumo* @descriptions: 接雨水*/
public class TrappingRainWater {public static void main(String[] args) {// int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};int[] height = {0,3,0,2,1,0,1,1,2,1,2,1};System.out.println(trap0(height));System.out.println(trap1(height));System.out.println(trap2(height));}// 暴力遍歷解法public static int trap0(int[] height) {int n = height.length;if(n <= 1){return 0;}//定義兩個數組，分別存儲height[0,,,i]和height[i,,,n - 1]的最大值int[] leftMaxNum = new int[n];int[] rightMaxNum = new int[n];//初始化leftMaxNum[0] = height[0];rightMaxNum[n - 1] = height[n - 1];//計算i左側的最大值for(int i = 1; i < n; i++){leftMaxNum[i] = Math.max(leftMaxNum[i - 1], height[i]);}for(int j = n - 2; j >= 0; j--){rightMaxNum[j] = Math.max(rightMaxNum[j + 1], height[j]);}//遍歷計算每個位置能接住的雨水量int res = 0;for(int k = 1; k < n - 1; k++){res += Math.min(leftMaxNum[k], rightMaxNum[k]) - height[k];}return res;}//雙指針static int trap2(int[] height) {// 總數int ans = 0;int left = 0;int right = height.length - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = Math.max(leftMax, height[left]);rightMax = Math.max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}}
)
