題目
給定 n 個非負整數表示每個寬度為 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 個單位的雨水（藍色部分表示雨水）。
輸入：height = [4,2,0,3,2,5]
輸出：9
鏈接：[https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked)
思路
思路一（超時）
暴力：對于每個位置，找到左右最高的高度，計算當前位置的雨水，加和。O(N2)會超時
思路二
在暴力的基礎上進行優化，先遍歷一遍提前知道每個位置左右最高高度，然后對于每個位置，計算當前位置的雨水，加和。O(N)
class Solution {public int trap(int[] height) {int sum = 0;int[] max_left = new int[height.length];int[] max_right = new int[height.length];// 提前知道每個位置左右最高高度for (int i = 1; i < height.length - 1; i++) {max_left[i] = Math.max(max_left[i - 1], height[i - 1]);}for (int i = height.length - 2; i >= 0; i--) {max_right[i] = Math.max(max_right[i + 1], height[i + 1]);}// 計算當前位置盛水量for (int i = 1; i < height.length - 1; i++) {int min = Math.min(max_left[i], max_right[i]);if (min > height[i]) {sum = sum + (min - height[i]);}}return sum;}
}
思路三
在思路二的基礎上繼續優化，在遍歷的過程中就知道左右最高高度，從而節省空間復雜度。
一個位置能盛放的雨水量，是由當前位置和**左右最高高度中較小的高度決定的。**因此，雙指針從頭尾進行遍歷，每次移動較矮的。在移動的過程中記錄水量。
class Solution {public int trap(int[] height) {int leftMax = height[0];int rightMax = height[height.length-1];int left = 0;int right = height.length-1;int sum = 0;while (left < right) {if (height[left] < height[right]) {leftMax = Math.max(leftMax, height[left]);sum = sum + leftMax - height[left];left++;} else {rightMax = Math.max(rightMax, height[right]);sum = sum + rightMax - height[right];right--;}}return sum;}
}
思路四（超時）
首先找到最高的高度max，在實際下雨的過程中，首先高度為1的地方都是水，然后是高度為2的地方都是水，依次到高度為max的地方。
那么對于當前的高度i，找到最左和最右高度為i的位置left和right。那么在這中間的這段區域都可能有水，比較每個位置的高度和i的關系即可，滿足則總水量+1。
class Solution {public int trap(int[] height) {int max = 0;for (int i = 0; i < height.length; i++) {max = Math.max(height[i], max);}int result = 0;for (int i = 1; i <= max; i++) {int left = 0;int right = height.length -1;while (left < right) {if (height[left] < i) {left++;} else if (height[right] < i) {right--;} else {for (int j = left+1; j < right; j++) {if (height[j] < i) {result++;}}break;}}}return result;}
}
)
