前言

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

---

接雨水

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

示例 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 個(gè)單位的雨水（藍(lán)色部分表示雨水）。
示例 2：

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

分析

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

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

代碼如下：

第一種方法：

class Solution {
public:// 接收一個(gè)整數(shù)數(shù)組 height，表示每個(gè)柱子的高度，返回可以接住的雨水總量int trap(vector<int>& height) {// n 表示柱子的總數(shù)int n = height.size();// res 用于存儲(chǔ)最終結(jié)果，也就是可以接住的雨水總量int res = 0;// 創(chuàng)建兩個(gè)數(shù)組，分別存儲(chǔ)每個(gè)位置的左邊最高柱子和右邊最高柱子vector<int> leftMax(n);  // leftMax[i] 表示位置 i 左邊最高的柱子vector<int> rightMax(n); // rightMax[i] 表示位置 i 右邊最高的柱子// 初始化 leftMax 數(shù)組的第一個(gè)元素，因?yàn)榈?0 個(gè)位置沒(méi)有左邊的柱子，所以 leftMax[0] 就是 height[0]leftMax[0] = height[0];// 計(jì)算每個(gè)位置的左邊最高柱子，從左到右遍歷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ù)組的最后一個(gè)元素，因?yàn)樽詈笠粋€(gè)位置沒(méi)有右邊的柱子，所以 rightMax[n-1] 就是 height[n-1]rightMax[n - 1] = height[n - 1];// 計(jì)算每個(gè)位置的右邊最高柱子，從右到左遍歷for(int i = n - 2; i > 0; i--) {// rightMax[i] 是當(dāng)前位置 i 和位置 i+1 的最高柱子之間的較大值rightMax[i] = max(rightMax[i + 1], height[i]);}// 遍歷每個(gè)柱子，計(jì)算該柱子上方能夠接住的雨水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，無(wú)法接住雨水，直接返回0if (n < 3) return 0;// 結(jié)果變量，用于存儲(chǔ)接住的雨水總量int res = 0;// 左指針初始化為數(shù)組的起始位置int left = 0;// 右指針初始化為數(shù)組的結(jié)束位置int right = n - 1;// 左邊最大值初始化為0int leftMax = 0;// 右邊最大值初始化為0int rightMax = 0;// 雙指針遍歷，直到兩個(gè)指針重合while (left < right) {// 更新左邊最大值leftMax = max(leftMax, height[left]);// 更新右邊最大值rightMax = max(rightMax, height[right]);// 如果左邊最大值小于右邊最大值，處理左邊的情況if (leftMax < rightMax) {// 當(dāng)前位置的水量 = 左邊最大值 - 當(dāng)前柱子的高度res += leftMax - height[left];// 左指針向右移動(dòng)left++;} // 如果右邊最大值小于等于左邊最大值，處理右邊的情況else {// 當(dāng)前位置的水量 = 右邊最大值 - 當(dāng)前柱子的高度res += rightMax - height[right];// 右指針向左移動(dòng)right--;}}// 返回接住的雨水總量return res;}
};

代碼解釋

第一種方法主要思路：

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

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

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

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

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

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

復(fù)雜度分析：

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

第二種方法主要思路：

1.初始化：

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

2.雙指針遍歷：

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

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

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

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

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

3.返回結(jié)果：

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

復(fù)雜度分析

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