給定n個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。
示例
上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個(gè)單位的雨水（藍(lán)色部分表示雨水）。
示例:
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
分析
看到這個(gè)就會(huì)想到木桶效應(yīng)，即所盛的水由短板決定。這里也是同理。
example
以上圖為例分析一下過(guò)程，從左至右開(kāi)始，位置1肯定是邊界，也就是說(shuō)位置1右邊部分的水位絕對(duì)不可能高于此，所以我們可以從此開(kāi)始遍歷，如果后一位置的高度低于位置1，則假設(shè)這里的水位可以與1齊平，然后往后到位置6，一看，這里的高度高于位置1，也就是說(shuō)，不管你6往后的洪水滔天，和位置1到5的水位無(wú)關(guān)，前面已經(jīng)固定了。那么繼續(xù)往后，由于不用考慮前面的，那么位置6相當(dāng)于變?yōu)榱宋恢?。但是到了位置8，此時(shí)最高為此位置，一直往后，到了位置12，由于位置12高度小于位置8，也就是說(shuō)之前的假設(shè)的水位不可能真的達(dá)到，需要減去部分水位，那需要怎么減？這里處理就會(huì)麻煩，那么為什么1到6不用考慮減去呢？因?yàn)?高于1，假如12的位置也高于8，那么也不用考慮減去。所以根據(jù)短板效應(yīng)，我們應(yīng)該用短的那塊高度做假設(shè)水位，即從高度低的向高度高的去移動(dòng)。
但是如果從左至右依次遍歷，除特殊情況，否則不可能始終從高度低的向高度高的走，所以不能從一端遍歷，需要從兩端同時(shí)遍歷。
偽代碼如下：
while(左端最高的位置在右端最高位置之前){
if(左端最高的高度<右端最高的高度){
左端位置向右移動(dòng)，如果此位置小于最高則并記錄下水位增加，否則此位置變?yōu)樽罡? }
else{
右端位置向左移動(dòng)，如果此位置小于最高則記錄下水位增加，否則次位置變?yōu)樽罡? }
}
Leetcode C++代碼實(shí)現(xiàn)如下:
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
if(len==0) return 0;
int ret=0;
int lindex = 0, rindex = len-1;
int left = height[lindex], right = height[rindex];
while(lindex<rindex){
if(left<right){
if(height[++lindex]<left){ret += left-height[lindex];}
else{left = height[lindex];}
}
else{
if(height[--rindex]<right){ret += right-height[rindex];}
else{right = height[rindex];}
}
}
return ret;
}
};
由于只遍歷了一次，且存儲(chǔ)空間和長(zhǎng)度無(wú)關(guān)，則時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，基本還是不錯(cuò)的。
