前言

記錄一下刷題歷程 力扣第42題 接雨水

---

接雨水

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

示例 1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）。
示例 2：

輸入：height = [4,2,0,3,2,5]
輸出：9

分析

我們首先可以想到的就是統(tǒng)計一列左邊和右邊所有柱子的最高高度，根據(jù)下圖我們可以知道左右最高高度較低的值與當(dāng)前柱子的高度差就是這一列能存儲的水的高度。這是第一種方法但是需要O(n)的空間復(fù)雜度，有沒有優(yōu)化空間呢，我們來看方法2.

第二種方法，我們其實并不需要同時計算左右兩邊的最高高度，假如說我們對于當(dāng)前列已經(jīng)知道了左側(cè)的最高高度，只要右側(cè)出現(xiàn)比左側(cè)高度還要高，那么左側(cè)的最高高度就一定是水體的頂部，然后我們可以計算該列的水體高度，我們從數(shù)組兩端向中間遍歷，分別計算左指針和左側(cè)最高高度，右指針和右側(cè)最高高度，找到對應(yīng)結(jié)果較低的那一列直接更新結(jié)果即可

代碼如下：

第一種方法：

class Solution {
public:// 接收一個整數(shù)數(shù)組 height，表示每個柱子的高度，返回可以接住的雨水總量int trap(vector<int>& height) {// n 表示柱子的總數(shù)int n = height.size();// res 用于存儲最終結(jié)果，也就是可以接住的雨水總量int res = 0;// 創(chuàng)建兩個數(shù)組，分別存儲每個位置的左邊最高柱子和右邊最高柱子vector<int> leftMax(n);  // leftMax[i] 表示位置 i 左邊最高的柱子vector<int> rightMax(n); // rightMax[i] 表示位置 i 右邊最高的柱子// 初始化 leftMax 數(shù)組的第一個元素，因為第 0 個位置沒有左邊的柱子，所以 leftMax[0] 就是 height[0]leftMax[0] = height[0];// 計算每個位置的左邊最高柱子，從左到右遍歷for(int i = 1; i < n - 1; i++) {// leftMax[i] 是當(dāng)前位置 i 和位置 i-1 的最高柱子之間的較大值leftMax[i] = max(leftMax[i - 1], height[i]);}// 初始化 rightMax 數(shù)組的最后一個元素，因為最后一個位置沒有右邊的柱子，所以 rightMax[n-1] 就是 height[n-1]rightMax[n - 1] = height[n - 1];// 計算每個位置的右邊最高柱子，從右到左遍歷for(int i = n - 2; i > 0; i--) {// rightMax[i] 是當(dāng)前位置 i 和位置 i+1 的最高柱子之間的較大值rightMax[i] = max(rightMax[i + 1], height[i]);}// 遍歷每個柱子，計算該柱子上方能夠接住的雨水for(int i = 1; i < n - 1; i++) {// 當(dāng)前位置的雨水容量等于左邊和右邊最高柱子之間的較小值減去當(dāng)前柱子的高度int capacity = min(leftMax[i], rightMax[i]) - height[i];// 累加結(jié)果，capacity 是該位置能接住的水res += capacity;}// 返回最終的接水量return res;}
};

第二種方法：

class Solution {
public:int trap(vector<int>& height) {// 獲取柱子的總數(shù)int n = height.size();// 如果柱子數(shù)小于3，無法接住雨水，直接返回0if (n < 3) return 0;// 結(jié)果變量，用于存儲接住的雨水總量int res = 0;// 左指針初始化為數(shù)組的起始位置int left = 0;// 右指針初始化為數(shù)組的結(jié)束位置int right = n - 1;// 左邊最大值初始化為0int leftMax = 0;// 右邊最大值初始化為0int rightMax = 0;// 雙指針遍歷，直到兩個指針重合while (left < right) {// 更新左邊最大值leftMax = max(leftMax, height[left]);// 更新右邊最大值rightMax = max(rightMax, height[right]);// 如果左邊最大值小于右邊最大值，處理左邊的情況if (leftMax < rightMax) {// 當(dāng)前位置的水量 = 左邊最大值 - 當(dāng)前柱子的高度res += leftMax - height[left];// 左指針向右移動left++;} // 如果右邊最大值小于等于左邊最大值，處理右邊的情況else {// 當(dāng)前位置的水量 = 右邊最大值 - 當(dāng)前柱子的高度res += rightMax - height[right];// 右指針向左移動right--;}}// 返回接住的雨水總量return res;}
};

代碼解釋

第一種方法主要思路：

1.對于每個柱子而言，能接住的水量取決于左邊最高的柱子和右邊最高的柱子，以及當(dāng)前位置柱子的高度。柱子能接住的水量是左、右柱子中較矮的那個減去當(dāng)前柱子的高度。

為了快速得到每個柱子左邊和右邊的最大值，我們通過預(yù)處理分別計算 leftMax 和 rightMax 數(shù)組。然后對于每個柱子，計算它上方可以接住的水量并累加到結(jié)果中。

2.首先，我們用兩個數(shù)組 leftMax 和 rightMax 分別記錄每個柱子左邊和右邊的最高柱子。

leftMax[i] 表示位置 i 左邊的最高柱子，包括 i 本身。
rightMax[i] 表示位置 i 右邊的最高柱子，包括 i 本身。

3.遍歷 height 數(shù)組計算每個位置的左邊最高值和右邊最高值。

對于每個位置的柱子，我們計算其能接住的雨水量：min(leftMax[i], rightMax[i]) - height[i]。
累加每個位置的水量得到最終結(jié)果。

復(fù)雜度分析：

時間復(fù)雜度：該算法需要遍歷三次數(shù)組，時間復(fù)雜度為 O(n)。
空間復(fù)雜度：需要額外的兩個數(shù)組存儲左邊和右邊的最大值，空間復(fù)雜度為 O(n)。
這就是該算法的基本思路和實現(xiàn)方式。

第二種方法主要思路：

1.初始化：

獲取 height 數(shù)組的大小 n，存儲在變量 n 中。
如果柱子的數(shù)量小于3（例如0、1或2個柱子），無法形成凹槽來接雨水，直接返回0。
初始化結(jié)果變量 res 為0，用于存儲計算得到的雨水總量。
初始化兩個指針 left 和 right 分別指向數(shù)組的起始和結(jié)束位置。
初始化 leftMax 和 rightMax 為0，用于記錄當(dāng)前左邊和右邊的最大高度。

2.雙指針遍歷：

當(dāng) left 指針小于 right 指針時進(jìn)行循環(huán)。
在每次循環(huán)中：
更新 leftMax 為當(dāng)前位置左指針?biāo)钢拥母叨扰c之前 leftMax 的最大值之間的較大值。
更新 rightMax 為當(dāng)前位置右指針?biāo)钢拥母叨扰c之前 rightMax 的最大值之間的較大值。

如果 leftMax 小于 rightMax，說明左邊的最高柱子更矮，處理左邊的情況：

計算當(dāng)前位置可以接住的雨水量，等于 leftMax 減去當(dāng)前柱子的高度。
將該雨水量累加到結(jié)果變量 res 中。
將左指針向右移動一位。

否則，說明右邊的最高柱子更矮或相等，處理右邊的情況：

計算當(dāng)前位置可以接住的雨水量，等于 rightMax 減去當(dāng)前柱子的高度。
將該雨水量累加到結(jié)果變量 res 中。
將右指針向左移動一位。

3.返回結(jié)果：

循環(huán)結(jié)束后，返回最終計算得到的接水總量 res。

復(fù)雜度分析

時間復(fù)雜度：該算法的時間復(fù)雜度為 O(n)，因為每個柱子位置在循環(huán)中只會被訪問一次。
空間復(fù)雜度：該算法的空間復(fù)雜度為 O(1)，僅使用了常量級的額外空間，不需要額外的數(shù)組。
這個雙指針方法在時間復(fù)雜度和空間復(fù)雜度上都具有較好的性能，是處理這個問題的一種高效解法。