題目描述（困難難度）

黑色的看成墻，藍(lán)色的看成水凫岖，寬度一樣，給定一個(gè)數(shù)組逢净，每個(gè)數(shù)代表從左到右墻的高度隘截，求出能裝多少單位的水。也就是圖中藍(lán)色正方形的個(gè)數(shù)汹胃。

解法一 按行求

這是我最開始想到的一個(gè)解法婶芭，提交后直接 AC 了，自己都震驚了着饥。就是先求高度為 1 的水犀农，再求高度為 2 的水，再求高度為 3 的水宰掉。

整個(gè)思路就是呵哨，求第 i 層的水赁濒，遍歷每個(gè)位置，如果當(dāng)前的高度小于 i孟害，并且兩邊有高度大于等于 i 的拒炎，說明這個(gè)地方一定有水，水就可以加 1挨务。

如果求高度為 i 的水击你，首先用一個(gè)變量 temp 保存當(dāng)前累積的水，初始化為 0 谎柄。從左到右遍歷墻的高度丁侄，遇到高度大于等于 i 的時(shí)候，開始更新 temp朝巫。更新原則是遇到高度小于 i 的就把 temp 加 1鸿摇，遇到高度大于等于 i 的渐逃，就把 temp 加到最終的答案 ans 里尚猿，并且 temp 置零抡诞，然后繼續(xù)循環(huán)洽瞬。

我們就以題目的例子講一下。

先求第 1 行的水蟆融。

也就是紅色區(qū)域中的水朱嘴，數(shù)組是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 返奉。

原則是高度小于 1变逃，temp ++必逆，高度大于等于 1怠堪，ans = ans + temp揽乱，temp = 0。

temp 初始化為 0 粟矿，ans = 0

height [ 0 ] 等于 0 < 1凰棉，不更新。

height [ 1 ] 等于 1 >= 1陌粹，開始更新 temp撒犀。

height [ 2 ] 等于 0 < 1， temp = temp + 1 = 1掏秩。

height [ 3 ] 等于 2 >= 1或舞， ans = ans + temp = 1，temp = 0蒙幻。

height [ 4 ] 等于 1 >= 1映凳，ans = ans + temp = 1，temp = 0邮破。

height [ 5 ] 等于 0 < 1诈豌， temp = temp + 1 = 1仆救。

height [ 6 ] 等于 1 >= 1，ans = ans + temp = 2矫渔，temp = 0彤蔽。

剩下的 height [ 7 ] 到最后，高度都大于等于 1庙洼，更新 ans = ans + temp = 2顿痪，temp = 0。而其實(shí) temp 一直都是 0 送膳，所以 ans 沒有變化员魏。

再求第 2 行的水。

也就是紅色區(qū)域中的水叠聋，

數(shù)組是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 撕阎。

原則是高度小于 2，temp ++碌补，高度大于等于 2虏束，ans = ans + temp，temp = 0厦章。

temp 初始化為 0 镇匀，ans 此時(shí)等于 2。

height [ 0 ] 等于 0 < 2袜啃，不更新汗侵。

height [ 1 ] 等于 1 < 2，不更新群发。

height [ 2 ] 等于 0 < 2晰韵， 不更新。

height [ 3 ] 等于 2 >= 2熟妓， 開始更新

height [ 4 ] 等于 1 < 2雪猪，temp = temp + 1 = 1。

height [ 5 ] 等于 0 < 2起愈， temp = temp + 1 = 2只恨。

height [ 6 ] 等于 1 < 2， temp = temp + 1 = 3抬虽。

height [ 7 ] 等于 3 >= 2官觅， ans = ans + temp = 5，temp = 0阐污。

height [ 8 ] 等于 2 >= 2休涤， ans = ans + temp = 3，temp = 0疤剑。

height [ 9 ] 等于 1 < 2滑绒， temp = temp + 1 = 1闷堡。

height [ 10 ] 等于 2 >= 2， ans = ans + temp = 6疑故，temp = 0杠览。

height [ 11 ] 等于 1 < 2， temp = temp + 1 = 1纵势。

然后結(jié)束循環(huán)踱阿，此時(shí)的 ans 就是 6。

再看第 3 層钦铁。

按照之前的算法软舌，之前的都是小于 3 的，不更新 temp牛曹，然后到 height [ 7 ] 等于 3佛点，開始更新 temp，但是后邊沒有 height 大于等于 3 了黎比，所以 ans 沒有更新超营。

所以最終的 ans 就是 6。

看下代碼吧阅虫。

public int trap(int[] height) {
    int sum = 0;
    int max = getMax(height);//找到最大的高度演闭，以便遍歷。
    for (int i = 1; i <= max; i++) {
        boolean isStart = false; //標(biāo)記是否開始更新 temp
        int temp_sum = 0;
        for (int j = 0; j < height.length; j++) {
            if (isStart && height[j] < i) {
                temp_sum++;
            }
            if (height[j] >= i) {
                sum = sum + temp_sum;
                temp_sum = 0;
                isStart = true;
            }
        }
    }
    return sum;
}

private int getMax(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length; i++) {
        if (height[i] > max) {
            max = height[i];
        }
    }
    return max;
}

時(shí)間復(fù)雜度：如果最大的數(shù)是 m颓帝，個(gè)數(shù)是 n米碰，那么就是 O（m * n）。

空間復(fù)雜度： O （1）购城。

經(jīng)過他人提醒吕座，這個(gè)解法現(xiàn)在 AC 不了了，會(huì)報(bào)超時(shí)工猜，但還是放在這里吧米诉。 下邊講一下菱蔬， leetcode solution 提供的 4 個(gè)算法篷帅。

解法二 按列求

求每一列的水，我們只需要關(guān)注當(dāng)前列拴泌，以及左邊最高的墻魏身，右邊最高的墻就夠了。

裝水的多少蚪腐，當(dāng)然根據(jù)木桶效應(yīng)箭昵，我們只需要看左邊最高的墻和右邊最高的墻中較矮的一個(gè)就夠了。

所以回季，根據(jù)較矮的那個(gè)墻和當(dāng)前列的墻的高度可以分為三種情況家制。

• 較矮的墻的高度大于當(dāng)前列的墻的高度

  把正在求的列左邊最高的墻和右邊最高的墻確定后正林，然后為了方便理解，我們把無關(guān)的墻去掉颤殴。

  這樣就很清楚了觅廓，現(xiàn)在想象一下，往兩邊最高的墻之間注水涵但。正在求的列會(huì)有多少水杈绸？

  很明顯，較矮的一邊矮瘟，也就是左邊的墻的高度瞳脓，減去當(dāng)前列的高度就可以了，也就是 2 - 1 = 1澈侠，可以存一個(gè)單位的水劫侧。

• 較矮的墻的高度小于當(dāng)前列的墻的高度

  同樣的，我們把其他無關(guān)的列去掉哨啃。

  想象下板辽，往兩邊最高的墻之間注水。正在求的列會(huì)有多少水棘催？

  正在求的列不會(huì)有水劲弦，因?yàn)樗笥诹藘蛇呡^矮的墻。

• 較矮的墻的高度等于當(dāng)前列的墻的高度醇坝。

  和上一種情況是一樣的邑跪，不會(huì)有水。

明白了這三種情況呼猪，程序就很好寫了画畅，遍歷每一列，然后分別求出這一列兩邊最高的墻宋距。找出較矮的一端轴踱，和當(dāng)前列的高度比較，結(jié)果就是上邊的三種情況谚赎。

public int trap(int[] height) {
    int sum = 0;
    //最兩端的列不用考慮淫僻，因?yàn)橐欢ú粫?huì)有水。所以下標(biāo)從 1 到 length - 2
    for (int i = 1; i < height.length - 1; i++) {
        int max_left = 0;
        //找出左邊最高
        for (int j = i - 1; j >= 0; j--) {
            if (height[j] > max_left) {
                max_left = height[j];
            }
        }
        int max_right = 0;
        //找出右邊最高
        for (int j = i + 1; j < height.length; j++) {
            if (height[j] > max_right) {
                max_right = height[j];
            }
        }
        //找出兩端較小的
        int min = Math.min(max_left, max_right);
        //只有較小的一段大于當(dāng)前列的高度才會(huì)有水壶唤，其他情況不會(huì)有水
        if (min > height[i]) {
            sum = sum + (min - height[i]);
        }
    }
    return sum;
}

時(shí)間復(fù)雜度：O（n2）雳灵，遍歷每一列需要 n，找出左邊最高和右邊最高的墻加起來剛好又是一個(gè) n闸盔，所以是 n2悯辙。

空間復(fù)雜度：O（1）。

解法三 動(dòng)態(tài)規(guī)劃

我們注意到，解法二中躲撰。對(duì)于每一列针贬，我們求它左邊最高的墻和右邊最高的墻，都是重新遍歷一遍所有高度拢蛋，這里我們可以優(yōu)化一下坚踩。

首先用兩個(gè)數(shù)組，max_left [ i ] 代表第 i 列左邊最高的墻的高度瓤狐，max_right [ i ] 代表第 i 列右邊最高的墻的高度瞬铸。（一定要注意下，第 i 列左（右）邊最高的墻础锐，是不包括自身的嗓节，和 leetcode 上邊的講的有些不同）

對(duì)于 max_left 我們其實(shí)可以這樣求。

max_left [ i ] = Max ( max_left [ i - 1] , height [ i - 1]) 皆警。它前邊的墻的左邊的最高高度和它前邊的墻的高度選一個(gè)較大的拦宣，就是當(dāng)前列左邊最高的墻了。

對(duì)于 max_right我們可以這樣求信姓。

max_right[ i ] = Max ( max_right[ i + 1] , height [ i + 1]) 鸵隧。它后邊的墻的右邊的最高高度和它后邊的墻的高度選一個(gè)較大的，就是當(dāng)前列右邊最高的墻了意推。

這樣豆瘫，我們再利用解法二的算法，就不用在 for 循環(huán)里每次重新遍歷一次求 max_left 和 max_right 了菊值。

public int trap(int[] height) {
    int sum = 0;
    int[] max_left = new int[height.length];
    int[] max_right = new int[height.length];
    
    for (int i = 1; i < height.length - 1; i++) {
        max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
    }
    for (int i = height.length - 2; i >= 0; i--) {
        max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
    }
    for (int i = 1; i < height.length - 1; i++) {
        int min = Math.min(max_left[i], max_right[i]);
        if (min > height[i]) {
            sum = sum + (min - height[i]);
        }
    }
    return sum;
}

時(shí)間復(fù)雜度：O（n）外驱。

空間復(fù)雜度：O（n），用來保存每一列左邊最高的墻和右邊最高的墻腻窒。

解法四 雙指針

動(dòng)態(tài)規(guī)劃中昵宇，我們常常可以對(duì)空間復(fù)雜度進(jìn)行進(jìn)一步的優(yōu)化儿子。

例如這道題中瓦哎，可以看到，max_left [ i ] 和 max_right [ i ] 數(shù)組中的元素我們其實(shí)只用一次柔逼，然后就再也不會(huì)用到了蒋譬。所以我們可以不用數(shù)組，只用一個(gè)元素就行了卒落。我們先改造下 max_left羡铲。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int[] max_right = new int[height.length];
    for (int i = height.length - 2; i >= 0; i--) {
        max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
    }
    for (int i = 1; i < height.length - 1; i++) {
        max_left = Math.max(max_left, height[i - 1]);
        int min = Math.min(max_left, max_right[i]);
        if (min > height[i]) {
            sum = sum + (min - height[i]);
        }
    }
    return sum;
}

我們成功將 max_left 數(shù)組去掉了蜂桶。但是會(huì)發(fā)現(xiàn)我們不能同時(shí)把 max_right 的數(shù)組去掉儡毕，因?yàn)樽詈蟮?for 循環(huán)是從左到右遍歷的，而 max_right 的更新是從右向左的。

所以這里要用到兩個(gè)指針腰湾，left 和 right雷恃，從兩個(gè)方向去遍歷。

那么什么時(shí)候從左到右费坊，什么時(shí)候從右到左呢倒槐？根據(jù)下邊的代碼的更新規(guī)則，我們可以知道

max_left = Math.max(max_left, height[i - 1]);

height [ left - 1] 是可能成為 max_left 的變量附井， 同理讨越，height [ right + 1 ] 是可能成為 right_max 的變量。

只要保證 height [ left - 1 ] < height [ right + 1 ] 永毅，那么 max_left 就一定小于 max_right把跨。

因?yàn)?max_left 是由 height [ left - 1] 更新過來的，而 height [ left - 1 ] 是小于 height [ right + 1] 的沼死，而 height [ right + 1 ] 會(huì)更新 max_right着逐，所以間接的得出 max_left 一定小于 max_right。

反之意蛀，我們就從右到左更耸别。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;
    int right = height.length - 2; // 加右指針進(jìn)去
    for (int i = 1; i < height.length - 1; i++) {
        //從左到右更
        if (height[left - 1] < height[right + 1]) {
            max_left = Math.max(max_left, height[left - 1]);
            int min = max_left;
            if (min > height[left]) {
                sum = sum + (min - height[left]);
            }
            left++;
        //從右到左更
        } else {
            max_right = Math.max(max_right, height[right + 1]);
            int min = max_right;
            if (min > height[right]) {
                sum = sum + (min - height[right]);
            }
            right--;
        }
    }
    return sum;
}

時(shí)間復(fù)雜度： O（n）。

空間復(fù)雜度： O（1）县钥。

解法五 棧

說到棧秀姐，我們肯定會(huì)想到括號(hào)匹配了。我們仔細(xì)觀察藍(lán)色的部分若贮，可以和括號(hào)匹配類比下囊扳。每次匹配出一對(duì)括號(hào)（找到對(duì)應(yīng)的一堵墻），就計(jì)算這兩堵墻中的水兜看。

我們用棧保存每堵墻锥咸。

當(dāng)遍歷墻的高度的時(shí)候，如果當(dāng)前高度小于棧頂?shù)膲Ω叨认敢疲f明這里會(huì)有積水搏予，我們將墻的高度的下標(biāo)入棧。

如果當(dāng)前高度大于棧頂?shù)膲Φ母叨然≡f明之前的積水到這里停下雪侥，我們可以計(jì)算下有多少積水了。計(jì)算完精绎，就把當(dāng)前的墻繼續(xù)入棧速缨，作為新的積水的墻。

總體的原則就是代乃，

1. 當(dāng)前高度小于等于棧頂高度旬牲，入棧仿粹，指針后移。

2. 當(dāng)前高度大于棧頂高度原茅，出棧吭历，計(jì)算出當(dāng)前墻和棧頂?shù)膲χg水的多少，然后計(jì)算當(dāng)前的高度和新棧的高度的關(guān)系擂橘，重復(fù)第 2 步晌区。直到當(dāng)前墻的高度不大于棧頂高度或者棧空通贞，然后把當(dāng)前墻入棧朗若，指針后移。

我們看具體的例子昌罩。

• 首先將 height [ 0 ] 入棧捡偏。然后 current 指向的高度大于棧頂高度，所以把棧頂 height [ 0 ] 出棧峡迷，然后椧埃空了，再把 height [ 1 ] 入棧绘搞。current 后移彤避。

• 然后 current 指向的高度小于棧頂高度，height [ 2 ] 入棧夯辖，current 后移琉预。

• 然后 current 指向的高度大于棧頂高度，棧頂 height [ 2 ] 出棧蒿褂。計(jì)算 height [ 3 ] 和新的棧頂之間的水圆米。計(jì)算完之后繼續(xù)判斷 current 和新的棧頂?shù)年P(guān)系。

• current 指向的高度大于棧頂高度啄栓，棧頂 height [ 1 ] 出棧娄帖，棧空昙楚。所以把 height [ 3 ] 入棧近速。 currtent 后移。

• 然后 current 指向的高度小于棧頂 height [ 3 ] 的高度堪旧，height [ 4 ] 入棧削葱。current 后移。

• 然后 current 指向的高度小于棧頂 height [ 4 ] 的高度淳梦，height [ 5 ] 入棧析砸。current 后移。

• 然后 current 指向的高度大于棧頂 height [ 5 ] 的高度爆袍，將棧頂 height [ 5 ] 出棧首繁，然后計(jì)算 current 指向的墻和新棧頂 height [ 4 ] 之間的水作郭。計(jì)算完之后繼續(xù)判斷 current 的指向和新棧頂?shù)年P(guān)系。此時(shí) height [ 6 ] 不大于棧頂 height [ 4 ] 蛮瞄，所以將 height [ 6 ] 入棧所坯。 current 后移谆扎。

• 然后 current 指向的高度大于棧頂高度挂捅，將棧頂 height [ 6 ] 出棧。計(jì)算和新的棧頂 height [ 4 ] 組成兩個(gè)邊界中的水堂湖。然后判斷 current 和新的棧頂 height [ 4 ] 的關(guān)系闲先，依舊是大于，所以把 height [ 4 ] 出棧无蜂。計(jì)算current 和 新的棧頂 height [ 3 ] 之間的水伺糠。然后判斷 current 和新的棧頂 height [ 3 ] 的關(guān)系，依舊是大于斥季，所以把 height [ 3 ] 出棧训桶，棧空酣倾。將 current 指向的 height [ 7 ] 入棧舵揭。current 后移。

  其實(shí)不停的出棧躁锡，可以看做是在找與 7 匹配的墻午绳，也就是 3 。

而對(duì)于計(jì)算 current 指向墻和新的棧頂之間的水映之，根據(jù)圖的關(guān)系拦焚，我們可以直接把這兩個(gè)墻當(dāng)做之前解法三的 max_left 和 max_right，然后之前彈出的棧頂當(dāng)做每次遍歷的 height [ i ] 杠输。水量就是 Min ( max _ left 赎败，max _ right ) - height [ i ]，只不過這里需要乘上兩個(gè)墻之間的距離蠢甲∶唬可以看下代碼繼續(xù)理解下。

public int trap6(int[] height) {
    int sum = 0;
    Stack<Integer> stack = new Stack<>();
    int current = 0;
    while (current < height.length) {
        //如果棧不空并且當(dāng)前指向的高度大于棧頂高度就一直循環(huán)
        while (!stack.empty() && height[current] > height[stack.peek()]) {
            int h = height[stack.peek()]; //取出要出棧的元素
            stack.pop(); //出棧
            if (stack.empty()) { // 椣康觯空就出去
                break; 
            }
            int distance = current - stack.peek() - 1; //兩堵墻之前的距離妓笙。
            int min = Math.min(height[stack.peek()], height[current]);
            sum = sum + distance * (min - h);
        }
        stack.push(current); //當(dāng)前指向的墻入棧
        current++; //指針后移
    }
    return sum;
}

時(shí)間復(fù)雜度：雖然 while 循環(huán)里套了一個(gè) while 循環(huán)，但是考慮到每個(gè)元素最多訪問兩次能岩，入棧一次和出棧一次寞宫，所以時(shí)間復(fù)雜度是 O（n）。

空間復(fù)雜度：O（n）拉鹃。棧的空間辈赋。

總

解法二到解法三鲫忍，利用動(dòng)態(tài)規(guī)劃，空間換時(shí)間钥屈，解法三到解法四悟民，優(yōu)化動(dòng)態(tài)規(guī)劃的空間，這一系列下來篷就，讓人心曠神怡射亏。

更多詳細(xì)通俗題解詳見 leetcode.wang 。