1.原題

42. 接雨水 - 力扣（LeetCode）

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

2.題目解析

這一題是經常被考到的一道算法題，其中最簡單最好用的方法就是雙指針，今天我們就以雙指針的角度來解決這一題！

2.1動態規劃寫法

我們先從動態規劃的角度引入雙指針的視角！

在計算數組height中下標i處接雨水量時，存在這樣一個規律：下雨后水在該位置能達到的最大高度，等同于i兩側高度中的最小值，而i處實際能承接的雨水量，就是這個最大高度減去height[i]的值。

如果采用最基礎的解決方式，針對數組height里的每一個元素，都需要分別朝左、右方向進行掃描，記錄下左右兩邊的最大高度，進而算出每個下標位置能承接的雨水量。若數組height長度為n，由于對每個下標位置進行左右掃描都要耗費O(n)的時間，最終整體的時間復雜度會達到O(n2) 。

這種基礎做法之所以耗時較長，根源在于對每個下標位置都要重復執行左右掃描操作。要是能提前獲取每個位置兩側的最大高度，就能將計算能接雨水總量的時間復雜度降至O(n)。借助動態規劃的思路，恰好可以在O(n)時間內預先處理并得到每個位置兩側的最大高度。

具體操作時，我們構建兩個長度同為n的數組leftMax和rightMax。其中，leftMax[i]代表從數組起始位置到下標i這一范圍內，height的最大高度；rightMax[i]則表示從下標i到數組末尾，height的最大高度。

不難發現，leftMax數組的第一個元素leftMax[0]，其值就等于height[0]；rightMax數組的最后一個元素rightMax[n - 1]，對應的值為height[n - 1]。至于兩個數組的其他元素，計算規則如下：

• 當1 ≤ i ≤ n - 1時，leftMax[i]取leftMax[i - 1]和height[i]中的較大值；

• 當0 ≤ i ≤ n - 2時，rightMax[i]是rightMax[i + 1]和height[i]中的較大值。

基于此，我們可以通過正向遍歷數組height，逐個算出leftMax數組的元素值；再反向遍歷數組height，得到rightMax數組的每個元素值。

在獲取leftMax和rightMax數組的全部元素值后，對于0 ≤ i < n范圍內的每個i，其下標位置能承接的雨水量就等于min(leftMax[i], rightMax[i]) - height[i]。最后，遍歷所有下標位置，將每個位置的接雨水量累加起來，便能得到最終能承接的雨水總量。

2.2引入雙指針寫法

在動態規劃解法中，需借助leftMax和rightMax兩個數組記錄各位置左右兩側的最大高度，這導致空間復雜度為O(n)。那么，能否進一步優化空間復雜度至O(1)呢？答案是肯定的。通過觀察發現，每個位置的儲水量僅由其左右兩側最大高度的較小值決定，而雙指針技術可巧妙利用這一特性，用兩個變量替代數組存儲中間狀態。

核心思路：雙指針與變量維護

我們引入兩個指針left和right，分別指向數組首尾兩端，同時用兩個變量left_max和right_max動態記錄當前左右指針處的歷史最大高度。具體邏輯如下：

1. 初始化：left = 0，right = n-1，left_max = 0，right_max = 0。

1. 指針移動規則：當height[left] < height[right]時，說明左側當前高度較低，其儲水量由左側歷史最大高度決定。此時計算left位置的儲水量，并右移left指針。當height[left] ≥ height[right]時，說明右側當前高度較低，其儲水量由右側歷史最大高度決定。此時計算right位置的儲水量，并左移right指針。
2. 動態更新最大高度：每次處理指針位置前，先更新對應方向的歷史最大高度（left_max或right_max）。

具體實現步驟

假設數組長度為n，初始時雙指針未相遇（left < right），循環執行以下操作：

1. 更新歷史最大高度：
2. left_max = max(left_max, height[left])
3. right_max = max(right_max, height[right])
4. 比較當前指針處高度：
5. 若height[left] < height[right]：
6. 此時左側最大高度left_max必然小于等于右側最大高度right_max（因height[left]是較小值），故left位置的儲水量為 left_max - height[left]。
7. 將該值累加到總儲水量，然后left++。
8. 若height[left] ≥ height[right]：
9. 此時右側最大高度right_max必然小于等于左側最大高度left_max，故right位置的儲水量為 right_max - height[right]。
10. 將該值累加到總儲水量，然后right--。
11. 循環終止條件：當left == right時，遍歷結束，返回總儲水量。

關鍵邏輯推導

• 為什么可以用單變量替代數組？當height[left] < height[right]時，left位置的右側最大高度至少為height[right]（后續right指針左移可能遇到更高高度），但儲水量由左右兩側的較小值決定。由于height[left]是當前較小值，其左側最大高度left_max已確定為左側全局最大值，因此無需記錄右側所有位置的最大值，只需保證left_max是左側歷史最大值即可。同理適用于右側情況。

復雜度分析

• 時間復雜度：O(n)，每個元素僅被左右指針各訪問一次。

• 空間復雜度：O(1)，僅使用常數級額外空間（指針和變量）。

總結

通過雙指針技術，我們避免了存儲兩個完整數組，將空間復雜度從O(n)優化至O(1)，同時保持線性時間復雜度。該解法的核心在于利用左右指針的相對高度關系，動態確定當前位置的儲水量由哪一側的最大高度主導，從而實現空間效率的顯著提升。

3.雙指針寫法代碼

class Solution {
public:int trap(vector<int>& v) {int n=v.size();int l=0;int r=n-1;int ans=0;int lmax=0,rmax=0;while(l<=r){lmax=max(lmax,v[l]);rmax=max(rmax,v[r]);if(v[r]>=v[l]){ans+=lmax-v[l];l++;}else {ans+=rmax-v[r];r--;}}return ans;}
};

本題解為參考力扣題解后的總結！