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

解法一 暴力法
思路：
1、初始化ans = 0；
2、遍歷數(shù)組；
（1）遍歷該值左邊，找到左邊數(shù)組最大值
（2）遍歷該值右邊，找到右邊數(shù)組最大值
（3）取左右最大值的較小值，減去當前高度，累加到ans

var trap = function(height) {
    let ans = 0;
    for(let i = 1, len = height.length; i < len - 1; i ++){
        let left_max = 0, right_max = 0;
        for (let left = 0; left <= i; left ++){
            left_max = Math.max(left_max, height[left]);
        }
        for (let right = len - 1; right >= i; right --){
            right_max = Math.max(right_max, height[right]);
        }
        ans += Math.min(left_max, right_max) - height[i]
    }
    return ans;
};

解法二 動態(tài)規(guī)劃
思路：
1、基于以上遍歷尋找每個元素的左右最大值，可優(yōu)化為記錄從開端到當前位置為止的最大高度，從左右兩個順序開始；
2、遍歷數(shù)組，取當前位置上左右兩個最大值中較小的那個，減去當前高度，累加到ans；

var trap = function(height) {
    let ans = 0,
        len = height.length;
        left_max = [], 
        right_max = [];

    left_max[0] = height[0];
    right_max[len - 1] = height[len - 1];

    for (let i = 1; i < len; i ++){
        left_max[i] = Math.max(left_max[i - 1], height[i]);
    }
    for (let i = len - 2; i >= 0; i --){
        right_max[i] = Math.max(right_max[i + 1], height[i]);
    }
    for (let i = 1; i < len - 1; i ++){
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
        
    return ans;
};

解法三 雙指針
思路：
在解法二的基礎(chǔ)上，優(yōu)化最大高度左右兩側(cè)較大的部分，將循環(huán)簡化為一次；
1、從左到右遍歷時，如果當前值比左側(cè)最大值大，則當前位置沒有雨水，更新最大值；如果比左側(cè)最大值小，則該位置會貯存雨水，雨水高度為左側(cè)最大值減去當前高度；
2、從右到左反之
過程參考下圖，圖片來源于力扣官網(wǎng)。

var trap = function(height) {
    let ans = 0,
        len = height.length;
        left = 0, 
        right = len - 1,
        left_max = right_max = 0;

    while(left < right){
        if(height[left] < height[right]){
            height[left] > left_max ? left_max = height[left] : ans += left_max - height[left];
            left ++;
        }else{
            height[right] > right_max ? right_max = height[right] : ans += right_max - height[right];
            right --;
        }
    }
   
    return ans;
};

解法四 棧
思路：
之前的思路都是累加每一列的雨水深度，該方法在每個水洼處逐行累加；
1、初始化一個棧
2、遍歷
（1）如果當前高度比棧頂元素小，將當前索引壓棧
（2）如果當前高度比棧頂元素大，彈出棧頂元素；記錄當前高度與彈出后棧頂索引對應(yīng)高度的最大值，減去當前被彈出的索引值，作為高度；計算當前索引與彈出后棧頂索引中間的距離，作為長度；計算長*高，累加到ans；重復(fù)（2）直到棧頂索引對應(yīng)高度大于等于當前高度

var trap = function(height){
    let ans = 0, current = 0;
    let stack = [];
    while (current < height.length) {
        while (!!stack.length && height[current] > height[stack[stack.length - 1]]) {
            let top = stack.pop();
            if (!stack.length)
                break;
            let distance = current - stack[stack.length - 1] - 1;
            let bounded_height = Math.min(height[current], height[stack[stack.length - 1]]) - height[top];
            ans += distance * bounded_height;
        }
        stack.push(current++);
    }
    return ans;
}