給定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
以上圖為例分析一下過程渺绒，從左至右開始贺喝，位置1肯定是邊界，也就是說位置1右邊部分的水位絕對(duì)不可能高于此宗兼，所以我們可以從此開始遍歷躏鱼，如果后一位置的高度低于位置1，則假設(shè)這里的水位可以與1齊平殷绍，然后往后到位置6挠他，一看，這里的高度高于位置1篡帕，也就是說殖侵，不管你6往后的洪水滔天贸呢，和位置1到5的水位無關(guān)，前面已經(jīng)固定了拢军。那么繼續(xù)往后楞陷，由于不用考慮前面的，那么位置6相當(dāng)于變?yōu)榱宋恢?茉唉。但是到了位置8固蛾，此時(shí)最高為此位置，一直往后度陆，到了位置12艾凯，由于位置12高度小于位置8，也就是說之前的假設(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)度無關(guān)空执，則時(shí)間復(fù)雜度為O(n)浪箭，空間復(fù)雜度為O(1)，基本還是不錯(cuò)的辨绊。
