什么時候能用雙指針？

（1）對撞指針：

①兩數和問題中可以使用雙指針，先將兩數和升序排序，可以發現規律，如果當前兩數和大于target，則右指針向左走。

②接雨水問題中，左邊最大?和?右邊最大?可以通過雙指針 +?雙變量維護。

（2）快慢指針：

①比如找到鏈表的中點，快指針一次走兩步，滿指針一次走一步。

（3）滑動窗口：

滑動窗口維護當前窗口內滿足要求。而雙指針可以在整個數組中考慮問題。

①比如接雨水這里，考慮窗口極限：滿足右邊界大于等于左邊界，此時左邊界移動。

一、從單個水柱本身考慮

下標為i的水柱能接的雨水，取決于它左邊最高的水柱?和?右邊最高的水柱的最小值（包括它本身）。

? ? ? ? 為了理解這一性質，我們可以這樣想象：取出左邊最高和最邊最高的水柱，將其比作一個碗的邊界。中間坑坑洼洼，忽高忽低，高低錯落，碗面中的一個點的能接水的最高高度是多少呢？?就是碗邊界的最小值-該點的高度。

因此，從單個水柱考慮，我們只需要能夠求出這個問題即可。

一、動態規劃

我們定義兩個數組：

left_max[i]：表示從0~i?中?水柱高度的最大值

right_max[i]：?表示從i~height.size()-1中水柱高度的最大值

class Solution {
public:int trap(vector<int>& height) {int n=height.size();vector<int> left_max(n);vector<int> right_max(n);left_max[0]=height[0];right_max[n-1]=height[n-1];//求出左邊最大值for(int i=1;i<n;++i){left_max[i]=max(left_max[i-1],height[i]);}//求出右邊最大值for(int i=n-2;i>=0;--i){right_max[i]=max(right_max[i+1],height[i]);}long long ans=0;for(int i=0;i<n;++i){ans+=min(left_max[i],right_max[i])-height[i];}return ans;}
};

二、雙指針

class Solution {
public:int trap(vector<int>& height) {int n=height.size();int left_max=height[0];int right_max=height[n-1];int left=0;int right=n-1;long long ans=0;while(left<right){left_max=max(left_max,height[left]);right_max=max(right_max,height[right]);if(left_max>right_max){//說明右邊這個right柱子 取決于 其右邊的最高高度。ans+=right_max-height[right];--right;}else{ans+=left_max-height[left];++left;}}return ans;}
};

二、從整體水柱考慮

從左向右依次看，對于第一個水柱而言，直到遇到一個比它高的水柱，其中間的水柱都由第一個水柱的高度決定。一種特殊情況是，最后一個找不到比它高的水柱，此時對它我們從右往左看即可。（左右對稱）

class Solution {
public:int trap(vector<int>& height) {int left=0;//左邊指向當前左柱子，當左柱子低于右柱子時，它已經不再能裝水了 int right=1;//右邊往右一直尋找比左柱子高的 或 相等高度的柱子int sum=0;while(right<height.size()){if(height[right]>=height[left]){int temp=height[left];while(left!=right){sum+=temp-height[left];++left;}}++right;}if(left!=height.size()-1){int end=left;left=height.size()-1;right=left-1;while(right>=end){if(height[right]>=height[left]){int temp=height[left];while(left!=right){sum+=temp-height[left];--left;}}--right;}}return sum;}
};