一、問題描述：

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

二、解題思路：

思路1：通過動態規劃的預處理方式，分別計算每個柱子左右兩側的最大高度，然后通過遍歷計算每個柱子的位置能夠存儲的水量，最終求得總的積水量。

• 代碼示例：

public int trap(int[] height) {int length = height.length;if (length <= 2) return 0;int[] maxLeft = new int[length];int[] maxRight = new int[length];// 記錄每個柱子左邊柱子最大高度maxLeft[0] = height[0];for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);// 記錄每個柱子右邊柱子最大高度maxRight[length - 1] = height[length - 1];for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);// 求和int sum = 0;for (int i = 0; i < length; i++) {int count = Math.min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}

• 時間復雜度為 O(n)，空間復雜度為 O(n)，

思路2：用單調棧計算能接的雨水總量。

找到高-低-高形狀的凹槽。
通過維護一個單調棧，單調棧存儲的是下標，滿足從棧底到棧頂的下標對應的數組 height 中的元素遞減。
遍歷數組，只要當前遍歷的元素 height[i] 大于棧頂元素 height[top]，且棧中至少包含兩個元素，就可以形成一個“凹槽”，height[i] 是右邊界，top下面的元素是左邊界 height[left] 。
凹槽的儲水量 curheight = Math.min(height[left], height[i]) - height[top];

• 代碼示例：

public int trap(int[] height) {int result = 0;  // 存儲最終的接水量Deque<Integer> stack = new LinkedList<Integer>();  // 單調棧，存儲數組索引int n = height.length;  // 數組長度for(int i = 0; i < n; ++i) {// 當棧非空且當前柱子高度大于棧頂柱子高度時，可以接雨水while(!stack.isEmpty() && height[i] > height[stack.peek()]) {int top = stack.pop();  // 彈出棧頂元素，表示當前可以接水的高度if(stack.isEmpty()) break;int left = stack.peek();  // 左邊界，當前彈出元素的左邊界int curwidth = i - left - 1;  // 當前可以接水的寬度// 當前可以接水的高度，即左右邊界的最小高度減去當前彈出元素的高度int curheight = Math.min(height[left], height[i]) - height[top];// 累加當前可以接水的體積//System.out.println(i +" " + left + " " + top + " " + curwidth * curheight);result += curwidth * curheight;}stack.push(i);  // 將當前柱子索引壓入棧中}  return result;  // 返回最終的接水量}    

• 時間復雜度為 O(n)，空間復雜度也為 O(n)