題目鏈接：42. 接雨水 - 力扣（LeetCode）
這里我們可以用兩種方法去解決巧妙地解決這個題。首先來看一下題目
題目描述
給定?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
題目作答
核心解題思想
????????解決此問題的根本在于，對于數組中的任意一個位置 i，其上方能夠積蓄的雨水高度，取決于它左側所有柱子中的最高者 (left_max) 和右側所有柱子中的最高者 (right_max) 中較矮的那一個。這個較矮的高度決定了該位置的水位。
- 該位置 i 的最終水位高度為：water_level = min(?left_max, right_max)。
- 該位置 i 本身能存儲的雨水量為：water[i] = water_level - height[i]。（如果結果為負數，則該處蓄水量為0）
我們的目標就是求出所有位置的蓄水量的值再相加。
方法一：動態規劃
此方法通過預計算，直觀地實現了上述核心思想。
思路
- 預計算左側最大高度：創建一個數組 left_max_arr，長度與 height 相同。從左到右遍歷 height 數組，對于每個位置 i，left_max_arr[i] 存儲從索引 0 到 i 的所有柱子中的最大高度。
- 預計算右側最大高度：創建另一個數組 right_max_arr。這一次，我們從右到左遍歷 height 數組，對于每個位置 i，right_max_arr[i] 存儲從索引 i 到 n-1 的所有柱子中的最大高度。
- 計算總雨水量：當我們擁有了每個位置的左側最高和右側最高之后，就可以進行第三次遍歷。對于每個位置 i，其水位就是 min(left_max_arr[i], right_max_arr[i])。用這個水位減去當前柱子的高度 height[i]，就是該位置的蓄水量。將所有位置的蓄水量累加起來，即為最終答案。
圖片來源：毒瘤面試題：接雨水_嗶哩嗶哩_bilibili
復雜度分析
- 時間復雜度: O(n)。我們進行了三次獨立的線性遍歷，總時間復雜度為 O(n)+O(n)+O(n)=O(n)。
- 空間復雜度: O(n)。我們使用了兩個長度為 n 的額外數組 left_max_arr 和 right_max_arr 來存儲中間計算結果。
代碼如下
class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n < 3) {return 0;}// 1. left_max_arr 數組，記錄從左到右的最大值vector<int> left_max_arr(n);left_max_arr[0] = height[0];for (int i = 1; i < n; ++i) {left_max_arr[i] = max(left_max_arr[i - 1], height[i]);}// 2. right_max_arr 數組，記錄從右到左的最大值vector<int> right_max_arr(n);right_max_arr[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {right_max_arr[i] = max(right_max_arr[i + 1], height[i]);}// 3. 遍歷每個位置，計算并累加雨水int total_water = 0;for (int i = 0; i < n; ++i) {// 計算當前位置的水位int water_level = min(left_max_arr[i], right_max_arr[i]);// 累加當前位置的蓄水量total_water += water_level - height[i];}return total_water;}
};
方法二：分治法
此方法是動態規劃解法的空間優化版本，它在一次遍歷中就完成了所有計算，無需額外的存儲數組。
思路
第一步：找到全局最高點
????????首先，我們需要一次遍歷整個 height 數組，找到其中最高的柱子的高度 max_height 和其對應的索引 max_index。這個最高的柱子就像一座山峰，它自然地將整個地形分成了左、右兩個部分。在它左邊的區域，積水情況最多只會受到它本身以及它左邊的墻的影響；同理，右邊的區域也是如此。
第二步：處理左半部分（從數組開頭到最高點）
????????現在，我們從數組的最左邊（索引 0）開始，向右遍歷直到最高點所在的索引 max_index。
- 我們維護一個變量 left_max，用來記錄從左邊到當前位置為止遇到的最高墻體。
- 對于這個區間的任何一根柱子 height[i]，它右邊的最高墻一定是我們第一步找到的全局最高點 max_height。
- 因此，在該位置 i 的蓄水高度瓶頸，就完全取決于其左邊的最高墻 left_max。因為 left_max 不可能超過 max_height。
- 所以，在位置 i 的蓄水量就是 left_max - height[i]。
- 我們從左向右遍歷，不斷更新 left_max 并累加每個位置的蓄水量。
第三步：處理右半部分（從數組末尾到最高點）
????????處理完左邊，我們用完全對稱的邏輯來處理右半部分。
- 我們從數組的最右邊（索引 n-1）開始，向左遍歷直到最高點所在的索引 max_index。
- 我們維護一個變量 right_max，用來記錄從右邊到當前位置為止遇到的最高墻體。
- 對于這個區間的任何一根柱子 height[i]，它左邊的最高墻一定是全局最高點 max_height。
- 因此，在該位置 i 的蓄水高度瓶頸，就完全取決于其右邊的最高墻 right_max。
- 我們在遍歷過程中，不斷更新 right_max 并累加每個位置的蓄水量 right_max - height[i]。
將第二步和第三步計算出的蓄水量相加，就得到了最終的總量。
復雜度分析
- 時間復雜度: O(n)。
- 空間復雜度: O(1)。
class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n < 3) {return 0;}// 1. 找到全局最高點int max_height = 0;int max_index = 0;for (int i = 0; i < n; ++i) {if (height[i] > max_height) {max_height = height[i];max_index = i;}}int total_water = 0;// 2. 處理左半部分 (從 0 到 max_index)int left_max = 0;for (int i = 0; i < max_index; ++i) {// 更新左側遇到的最高墻left_max = max(left_max, height[i]);// 計算當前位置的蓄水量并累加total_water += left_max - height[i];}// 3. 處理右半部分 (從 n-1 到 max_index)int right_max = 0;for (int i = n - 1; i > max_index; --i) {right_max = max(right_max, height[i]);total_water += right_max - height[i];}return total_water;}
};
