題目描述：給 n 個(gè)非負(fù)整數(shù)表示的柱形圖谚殊，每個(gè)柱子寬度為1墓怀，計(jì)算雨后能存儲(chǔ)多少水。如：

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6

分析：對(duì)每個(gè)柱子找到其左右兩邊最高的柱子勋功，則這個(gè)柱子能容納的水的體積就是min(max_left， max_right)盟步。

方法一：對(duì)每個(gè)柱子

1. 從左往右掃描一遍，記錄其左側(cè)柱高的最大值

2. 從右往左掃描一遍躏结，記錄其右側(cè)柱高的最大值

3. 再從頭到尾掃一遍址芯，累加每個(gè)柱子可容納的體積

三次遍歷，時(shí)間復(fù)雜度O(n)窜觉，空間復(fù)雜度O(n)谷炸。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n < 3) return 0;
        
        int mxl[n] = {0}, mxr[n] = {0};           //分別記錄該柱子左右兩側(cè)的最高柱子的高度。數(shù)組需要顯示初始化為0禀挫，否則為隨機(jī)值旬陡。
        for (int i = 1; i < n; i ++)      //l 記錄從1 ~ (n - 1) ，r記錄從 0 ~ (n - 2)语婴。兩個(gè)過程遍歷方向相反但可在一次遍歷中完成
        {
            mxl[i] = max(mxl[i - 1], height[i - 1]);         //當(dāng)前柱子左側(cè)的最高高度為前一個(gè)柱子左側(cè)的最高高度與前一個(gè)柱子的高度的最大值
            mxr[n - 1 - i] = max(mxr[n - i], height[n - i]);            //下標(biāo)為 n - 1 - i 柱子右側(cè)的最高高度為其后一個(gè)柱子右側(cè)的最高高度與后一個(gè)柱子的高度的最大值
        }

        int s = 0;
        for (int i = 0; i < n; i++)
        {
            int ht = min(mxl[i], mxr[i]);       
            //cout<<mxl[i]<<" "<<mxr[i]<<endl;
            //cout<<ht<<endl;
            if (ht > height[i])         //若當(dāng)前柱子左右兩側(cè)最高高度的最小值比當(dāng)前柱子高度高描孟，則該柱上面缺失的部分都是存水的體積
                s += ht - height[i];
        }
        return s;
    }
};

方法二：

1. 遍歷一遍找到最高的柱子，該柱子將數(shù)組分為兩半

2. 處理左部分

3. 處理右部分

三次遍歷砰左，時(shí)間復(fù)雜度O(n)匿醒，空間復(fù)雜度O(1)。

class Solution {
public:
    int trap(vector<int>& height) {
        int mx = 0;          //記錄最高柱子的下標(biāo)
        int n = height.size();
        for (int i = 0; i < n; i ++)
            if (height[i] > height[mx])
                mx = i;

        int w = 0;            //記錄體積
        for (int i = 0, lp = 0; i < mx; i ++)        //從前往后遍歷左部分缠导，此時(shí)右側(cè)的最高高度已確定廉羔，lp記錄左側(cè)的最高高度
        {
            if (height[i] > lp)        //如果左側(cè)有更高的柱子，則提高標(biāo)尺
                lp = height[i];
            else
                w += lp - height[i];           //較低的柱子的上面是儲(chǔ)水的體積
        }
        for (int i = n - 1, rp = 0; i > mx; i --)          //從后往前遍歷右部分僻造，此時(shí)左側(cè)的最高高度已確定憋他，rp記錄右側(cè)的最高高度
        {
            if (height[i] > rp)         //如果右側(cè)有更高的柱子，則提高標(biāo)尺
                rp = height[i];
            else
                w += rp - height[i];
        }
        return w;
    }
};

方法三：用棧模擬髓削，每個(gè)柱子高度若小于棧頂元素則壓入竹挡，否則就把棧里所有小于等于當(dāng)前值的元素全部彈出并計(jì)算體積。時(shí)間復(fù)雜度O(n)立膛，空間復(fù)雜度O(n)揪罕。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<pair<int, int>> s;      //記錄下標(biāo)為 i
 的柱子的高度和下標(biāo) i 
        int w = 0;

        for (int i = 0; i < n; i ++)
        {
            int ht = 0;         //前一個(gè)棧頂?shù)闹?            while(!s.empty())
            {
                int bar = s.top().first;         //棧頂柱高
                int pos = s.top().second;    //棧頂柱下標(biāo)
                w += ( min(bar, height[i]) - ht ) * (i - pos - 1);
                ht = bar;
                
                if (height[i] < bar)       //當(dāng)前柱高小于棧頂元素高度，不需要進(jìn)棧宝泵，上一步已計(jì)算其上面能存水體積好啰，繼續(xù)處理下一個(gè)柱子
                    break;
                else
                    s.pop();        //否則遍歷處理、彈出所有比當(dāng)前柱高小的棧中元素
            }
            s.push(make_pair(height[i], i));
        }
        return w;
    }
};